Description

可怜的 ycc 在高中的时候就被灌输了很多数列求和的公式，并且多次在考试中被要求计算各种诡异的数列求和问题，因此在内心中留下了阴影 T_T

所以到大学了，他也不忘出一些数列求和的题目，坑害一下那些不擅长该类问题的小朋友们(⊙o⊙)

不过他不太忍心看着小朋友们一个一个板着脸，表现出一副“我不会做>_<”的样子。所以他会给出一些提示，帮助那些小朋友们顺利AC ^_^

我们已知如下公式：

1 + 2 + 3 + ... + (n - 1) + n = (n + 1) * n / 2

1^2 + 2^2 + 3^2 + ... + (n - 1)^2 + n^2 = n (n + 1) (2n + 1) / 6

1^3 + 2^3 + 3^3 + ... + (n - 1)^3 + n^3 = n^2 * (n + 1)^2 / 4

有了这些式子的帮助，那么你的任务就是计算下面这个式子的值：

• 1^k + 2^k - 3^k + ... + (-1)^n n^k = sigma_{i=1..n}{(-1)^i i^k}

注意到答案可能比较大，所以只要求与其模1000000007同余的最小非负整数就行了。

Input

第一行一个整数T，表示一共T组数据。每组数据占一行，有两个数n，k。其中1 <= n <= 10^9，1 <= k <= 60。

Output

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

Sample

Input

3
10 1
10 2
10 3

Output

5
55
575

Source: ycc