
ZOJ Problem Set  4006
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 \((x1)\), 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\). InputThere 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. OutputFor each test case output one integer, indicating the answer. Sample Input3 2 2 0 0 0 1 Sample Output562500004 1 0 Author: YE, Zicheng Source: ZOJ Monthly, March 2018 