H. Probability Theory
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Little L once encountered the following problem in a high school math quiz:

There is a staircase with $$$7$$$ steps. At each move, you may climb $$$1$$$ or $$$2$$$ steps. Find the probability of passing step $$$4$$$.

The reference solution was as follows:

Let $$$\textit{fib}_0=\textit{fib}_1=1$$$, and for $$$i\ge2$$$ let $$$\textit{fib}_i=\textit{fib}_{i-1}+\textit{fib}_{i-2}$$$. The answer is $$$\dfrac{\textit{fib}_4\cdot\textit{fib}_3}{\textit{fib}_7}=\dfrac{5}{7}$$$.

It assumes that all possible paths are equally likely. However, generally speaking, a person cannot directly choose one of the $$$\textit{fib}_7$$$ possible paths uniformly at random; instead, at each move, the person chooses to climb $$$1$$$ step or $$$2$$$ steps with equal probability (in particular, at step $$$6$$$, the person can only climb $$$1$$$ step).

To be rigorous, we restate the problem as follows:

There is a staircase with $$$7$$$ steps. A person wants to go from step $$$0$$$ to step $$$7$$$. At each move, the person climbs $$$1$$$ step with probability $$$\dfrac{1}{2}$$$, and $$$2$$$ steps with probability $$$\dfrac{1}{2}$$$. In particular, at step $$$6$$$, the person can only climb $$$1$$$ step. Find the probability of passing step $$$4$$$.

Consider drawing the probability tree, as shown in the following figure:

We can see that the answer should be $$$\dfrac{1}{16}+\dfrac{1}{8}+\dfrac{1}{8}+\dfrac{1}{8}+\dfrac{1}{4}=\dfrac{11}{16}$$$.

Now, consider a staircase with $$$n$$$ steps. A person wants to go from step $$$0$$$ to step $$$n$$$. At each move, the person climbs $$$1$$$ step with probability $$$\dfrac{1}{2}$$$, and $$$2$$$ steps with probability $$$\dfrac{1}{2}$$$. In particular, at step $$$n-1$$$, the person can only climb $$$1$$$ step. Find the probability of passing step $$$m$$$.

Print the answer modulo $$$10^9+7$$$ (a prime number).

Formally, it is easy to prove that the answer can be written as $$$\dfrac{p}{q}$$$. Here, $$$p$$$ is a non-negative integer, and $$$q$$$ is a positive integer that is not a multiple of $$$10^9+7$$$. You need to output $$$p\cdot q^{-1}\bmod(10^9+7)$$$, where $$$q^{-1}$$$ is an integer satisfying $$$q\cdot q^{-1}\equiv1\pmod{10^9+7}$$$. Modulo the prime number $$$10^9+7$$$, it is easy to prove that if $$$q^{-1}$$$ exists, then it is unique. According to Fermat's little theorem, $$$q^{-1}\equiv q^{10^9+5}\pmod{10^9+7}$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1\le T\le5$$$), denoting the number of test cases.

Then, for each test case, there is a single line containing two integers $$$n,m$$$ ($$$1\le m\le n\le10^{1000000}$$$).

Output

For each test case, output a single line containing one integer, the answer modulo $$$10^9+7$$$.

Example
Input
4
7 4
7 1
7 7
9876543210123456789 54321012345
Output
187500002
500000004
1
376896505
Note

For the first three test cases, the answers are $$$\dfrac{11}{16}$$$, $$$\dfrac{1}{2}$$$, and $$$1$$$, respectively.