405080: GYM101778 A Will he Die?

Unfortunately, Conan is in a real danger! Conan discovered who is the killer after searching for the evidence in a dangerous cave. Now, he is standing in front of a bomb that about to explode. The bomb will explode after m seconds.

The cave is represented as an infinite horizontal line that runs from  - ∞ to ∞, as shown in the picture below:

Initially, Conan stands at position 0. At each second, he will move either one step to the left (i.e. from position y to y - 1) or one step to the right (i.e. from position y to y + 1) with an equal probability (i.e. 0.50). Conan will be safe if he reached position n.

Conan is wondering what is the probability that he will be at position n after m seconds. Can you help Conan in calculating his chances of surviving?

The first line contains an integer T (1 ≤ T ≤ 10⁵), in which T is the number of test cases.

Then T lines follow, each line contains two integers n and m ( - 2 × 10⁵ ≤ n ≤ 2 × 10⁵) (0 ≤ m ≤ 2 × 10⁵), as described in the problem statement.

For each test case, print a single line containing z, in which z is the sought probability computed module 10⁹ + 7.

The answer z is defined precisely as follows. Represent the probability that Conan will be at position n after m seconds as an irreducible fraction p / q. The number z then must satisfy the modular equation , and be between 0 and 10⁹ + 6, inclusive. It can be shown that under the constraints of this problem such a number z always exists and is uniquely determined.

3
0 0
1 1
-3 3

1
500000004
125000001

In the second test case, Conan wants to know what is the probability that he will be at postilion 1 after 1 second of moving. The probability is 1 / 2, and the answer is 500000004, since .