描述

将a自加b次就是a*b,也即

a*b=\sum_{1}^{b}a

那么我们现在已经熟知了乘法的运算规律,下面我们将用它来做点事情。

T(n,x)=\sum_{k=0}^{n}(-1)^{n-k}*k^{x}

输入格式

输入为一行,n和x

输出格式

输出一个整数,表示T(n,x) Mod 10^9 + 7的值

样例输入

3 2

样例输出

6

数据范围与约定

  • 对于30%的数据:0\leq n\leq 100, 0\leq x\leq 100
  • 对于60%的数据:0\leq n\leq 10^{14}, 0\leq x\leq 10
  • 对于100%的数据:0\leq n\leq 10^{14}, 0\leq x\leq 1000
  • 最后请用非负整数输出

样例解释

 

来源