Family Hotel (Large)

You run a hotel with $N$ rooms arranged along one long corridor, numbered from 1 to $N$ along that corridor. Your guests are big families, and every family asks for exactly two adjacent rooms when they arrive. Two rooms are adjacent if their numbers differ by exactly 1.

At the start of the day today, your hotel was empty. You have been using the following simple strategy to assign rooms to your guests. As each family arrives, you consider all possible pairs of adjacent rooms that are both free, pick one of those pairs uniformly at random, and assign the two rooms in that pair to the family. New families constantly arrive, one family at a time, but once there are no more pairs of adjacent rooms that are both free, you turn on the NO VACANCY sign and you do not give out any more rooms.

Given a specific room number $K$, what is the probability that this room is occupied at the time you turn on the NO VACANCY sign?

The first line of the input gives the number of test cases, $T$. $T$ lines follow. Each line contains two numbers: the number of rooms $N$ and the room number $K$ that we are interested in.

Limits

• $1 \le T \le 100$
• $1 \le K \le N$
• $2 \le N \le 10^7$

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the sought probability computed modulo $10^9+7$, which is defined precisely as follows. Represent the probability that room $K$ is occupied as an irreducible fraction $p/q$. The number $y$ then must satisfy the modular equation $y \times q \equiv p \pmod{10^9+7}$, and be between 0 and $10^9+6$, inclusive. It can be shown that under the constraints of this problem such a number $y$ always exists and is uniquely determined.

In sample case #3, there are four rooms and we want the probability that the first room is occupied. When the first family arrives, there are 3 possible situations, each with probability 1/3: occupy rooms 1+2, 2+3 or 3+4. In the first situation, the first room is already occupied and stays occupied. In the second situation, the first room is free and no more families can be accommodated, so it stays free. Finally, in the third situation, the next arriving family definitely gets rooms 1+2, and thus the first room becomes occupied. The probability that the first room is occupied is thus 2/3, and the answer is 666666672, since (666666672 * 3) mod 1000000007 = 2 mod 1000000007.

The probability for sample case #1 is 1/2, and for sample cases #2 and #4 it is 1.