Expecting Edoce

Time Limit: 10 Seconds    Memory Limit: 65536 KB

“Edoce” is traveling along a line with infinite length. At the beginning of his trip, he is standing at position 0. At each second, if he is standing at position x, with 1/4 probability he will move to position x-1, with 1/4 probability he will move to position x+1, and with 1/2 probability he will stay at position x. Positions can be positive, 0, or negative.

“Rahs”, Edoce's best friend, is waiting for him at position m. Edoce would like to meet Rahs at position m after exactly n seconds. Please help Edoce calculate the probability he can get to position m after exactly n seconds.

It's easy to show that the answer can be represented as P/Q, where P and Q are coprime integers, and Q is not divisible by 109+7.

Print the value of PQ-1 modulo 109+7, where Q-1 is the multiplicative inverse of Q modulo 109+7.

Input

The first line of the input contains an integer T ≤ 16, indicating the number of test cases. For each test case, the first and only line contains two integers n and m (0 ≤ n, |m| ≤ 1015).

Output

For each test case output one integer, indicating the answer.

Sample Input

3
2 -2
0 0
0 1

Sample Output

562500004
1
0

Submit