Given N and K, compute () mod 1000000007.
The first line of the input gives an integer T, which is the number of test cases. Each test case consists of a line containing N (1 ≤ N ≤ 1000000000) and K (1 ≤ K ≤ 4).
For each test case output () mod 1000000007.