题目描述

You run a hotel with $\mathbf{N}$ rooms arranged along one long corridor, numbered from 1 to $\mathbf{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, what is the probability that it will be occupied at the time that you turn on the NO VACANCY sign?

输入格式

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

输出格式

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 $\mathbf{K}$ is occupied as an irreducible fraction $\frac{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.

4
3 1
3 2
4 1
4 2

Case #1: 500000004
Case #2: 1
Case #3: 666666672
Case #4: 1

提示

Sample Explanation

In sample case #3, there are four rooms and we are looking for 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 will stay occupied. In the second situation, the first room is free and no more families can be accommodated, so it will stay free. Finally, in the third situation, the next arriving family will definitely get rooms $1+2$, and thus the first room will be occupied. The probability that the first room is occupied is thus $2/3$, and the answer is $666666672$, since $(666666672 \times 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$.

Limits

• $1 \leqslant \mathbf{T} \leqslant 100$.
• $1 \leqslant \mathbf{K} \leqslant \mathbf{N}$.

Small dataset (10 Pts, Test Set 1 - Visible)

• $2 \leqslant \mathbf{N} \leqslant 10^{4}$.

Large dataset (20 Pts, Test Set 2 - Hidden)

• $2 \leqslant \mathbf{N} \leqslant 10^{7}$.