#描述#
可怜的 ycc 在高中的时候就被灌输了很多数列求和的公式，并且多次在考试中被要求计算各种诡异的数列求和问题，因此在内心中留下了阴影 T_T<BR>
所以到大学了，他也不忘出一些数列求和的题目，坑害一下那些不擅长该类问题的小朋友们(⊙o⊙)<BR>
不过他不太忍心看着小朋友们一个一个板着脸，表现出一副“我不会做><”的样子。所以他会给出一些提示，帮助那些小朋友们顺利AC ^^<BR>
我们已知如下公式：<BR>
1 + 2 + 3 + ... + (n - 1) + n = (n + 1) * n / 2<BR>
1^2 + 2^2 + 3^2 + ... + (n - 1)^2 + n^2 = n * (n + 1) * (2n + 1) / 6<BR>
1^3 + 2^3 + 3^3 + ... + (n - 1)^3 + n^3 = n^2 * (n + 1)^2 / 4<BR>
有了这些式子的帮助，那么你的任务就是计算下面这个式子的值：<BR>
- 1^k + 2^k - 3^k + ... + (-1)^n * n^k = sigma_{i=1..n}{(-1)^i * i^k}<BR>
注意到答案可能比较大，所以只要求与其模1000000007同余的最小非负整数就行了。

#格式#
##输入格式##
第一行一个整数T，表示一共T组数据。每组数据占一行，有两个数n，k。其中1 &lt= n &lt= 10^9，1 &lt= k &lt= 60。

##输出格式##
对于每组数据，输出一个答案，占一行。

#样例1#
##样例输入1##

3
10 1
10 2
10 3

##样例输出1##

5
55
575

#限制#
2000ms
32768KB

#提示#

#来源#
ycc