In this problem, we count the number of function f(x) satisfies below details.
1.f: M→M, ( M={-n,-n+1,-n+2,…,-1,0,1,…,n} )
2.∀x∈M,fk(x)=−x,(f0(x)=x,fi=f(fi−1)(i=1,2,…))
3.∀x∈M,|(|f(x)|−|x|)|≤2
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.
For each test case output the answer % 1000000007.
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).
