[Solution] Moamen and XOR solution codeforces

[Solution] Moamen and XOR solution codeforces

Moamen and Ezzat are playing a game. They create an array aa of nn non-negative integers where every element is less than 2k2k.

Moamen wins if a1&a2&a3&&ana1a2a3ana1&a2&a3&…&an≥a1⊕a2⊕a3⊕…⊕an.

Here && denotes the bitwise AND operation, and  denotes the bitwise XOR operation.

Please calculate the number of winning for Moamen arrays aa.

As the result may be very large, print the value modulo 10000000071000000007 (109+7109+7).

Input

The first line contains a single integer tt (1t51≤t≤5)— the number of test cases.

Each test case consists of one line containing two integers nn and kk (1n21051≤n≤2⋅1050k21050≤k≤2⋅105).

Output

For each test case, print a single value — the number of different arrays that Moamen wins with.

Print the result modulo 10000000071000000007 (109+7109+7).

Example
input

Copy
3
3 1
2 1
4 0

output

Copy
5
2
1

Note

In the first example, n=3n=3k=1k=1. As a result, all the possible arrays are [0,0,0][0,0,0][0,0,1][0,0,1][0,1,0][0,1,0][1,0,0][1,0,0][1,1,0][1,1,0][0,1,1][0,1,1][1,0,1][1,0,1], and [1,1,1][1,1,1].

Moamen wins in only 55 of them: [0,0,0][0,0,0][1,1,0][1,1,0][0,1,1][0,1,1][1,0,1][1,0,1], and [1,1,1][1,1,1].