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.$\forall x∈M, f_k (x)= -x,( f_0 (x)=x,f_i= f(f_{i-1} ) (i= 1,2,...) )$
3.$\forall 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.