Function Counting

Problem Description

Input

The first line of input contains an integer T (1 <= T <= 100) , the number of test cases. Each test case contains a pair of integers n, k (n * k <= $10^9$), the upper limit of the set M and degree of f. The total sum of n * k over all test cases does not exceed 4e9.

Output

For each test case output the answer % 1000000007.

Sample Input

7

1 1

2 1

100 1

1 2

2 2 

3 2

20 4

Sample Output

1

1

1

0

2

0

1048576

Hint

If k = 1, only one function f(x) = -x exists. If n = k = 2, two functions exist. f: (-2, -1, 0, 1, 2) -> (1, -2, 0, 2, -1) or (-1, 2, 0, -2, 1).

Source

2017 Multi-University Training Contest - Team 10

https://acm.hdu.edu.cn/showproblem.php?pid=6176