Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4006
Travel along the Line

Time Limit: 1 Second      Memory Limit: 65536 KB

BaoBao is traveling along a line with infinite length.

At the beginning of his trip, he is standing at position 0. At the beginning of each second, if he is standing at position $x$, with $\frac{1}{4}$ probability he will move to position $(x-1)$, with $\frac{1}{4}$ probability he will move to position $(x+1)$, and with $\frac{1}{2}$ probability he will stay at position $x$. Positions can be positive, 0, or negative.

DreamGrid, BaoBao's best friend, is waiting for him at position $m$. BaoBao would like to meet DreamGrid at position $m$ after exactly $n$ seconds. Please help BaoBao 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 $\frac{P}{Q}$, where $P$ and $Q$ are coprime integers, and $Q$ is not divisible by $10^9+7$. Please print the value of $PQ^{-1}$ modulo $10^9+7$, where $Q^{-1}$ is the multiplicative inverse of $Q$ modulo $10^9+7$.

#### Input

There are multiple test cases. The first line of the input contains an integer $T$ (about 10), indicating the number of test cases. For each test case:

The first and only line contains two integers $n$ and $m$ ($0 \le n, |m| \le 10^5$). Their meanings are described above.

#### 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


Author: YE, Zicheng
Source: ZOJ Monthly, March 2018
Submit    Status