Description

你经营着一家拥有 $\mathbf{N}$ 个房间的旅馆，这些房间沿着一条长走廊依次排列，编号为 $1$ 到 $\mathbf{N}$。你的客人都是大家庭，每个家庭到来时都会要求恰好两个相邻的房间。两个房间如果房号相差恰好为 $1$，则视为相邻。

今天一开始，旅馆是空的。你一直采用如下简单策略为客人分配房间：每当有家庭到来时，你会考虑所有当前仍然空闲且成对相邻的房间组合，从中等概率随机选择一对，将这两个房间分配给该家庭。新家庭会不断到来，每次只来一个，但一旦没有任何成对相邻且都空闲的房间，你就会亮起“无空房”标志，不再接待新客人。

现在，给定一个具体的房间号，问当你亮起“无空房”标志时，这个房间被占用的概率是多少？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 行，每行包含两个整数：房间总数 $\mathbf{N}$ 和你关心的房间号 $\mathbf{K}$。

Output Format

对于每组测试用例，输出一行 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为所求概率对 $10^9+7$ 取模后的值，具体定义如下。设房间 $\mathbf{K}$ 被占用的概率为最简分数 $\frac{p}{q}$，则 $y$ 应满足 $y \times q \equiv p \pmod{10^9+7}$，且 $y$ 在 $0$ 到 $10^9+6$ 之间。可以证明，在本题约束下，这样的 $y$ 总是存在且唯一。

4
3 1
3 2
4 1
4 2

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

Hint

样例解释

在样例第 3 组中，共有 4 个房间，我们关心第 1 个房间被占用的概率。第一个家庭到来时，有 3 种可能的分配（每种概率为 $1/3$）：入住 $1+2$、$2+3$ 或 $3+4$。第一种情况下，第 1 个房间立即被占用且之后不会再变；第二种情况下，第 1 个房间空着，且无法再安排其他家庭，因此始终空着；第三种情况下，下一个到来的家庭必然入住 $1+2$，从而第 1 个房间也会被占用。因此第 1 个房间被占用的概率为 $2/3$，答案为 $666666672$，因为 $(666666672 \times 3) \bmod 1000000007 = 2 \bmod 1000000007$。

样例第 1 组的概率为 $1/2$，第 2 组和第 4 组的概率均为 $1$。

限制条件

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

小数据集（10 分，测试集 1 - 可见）

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

大数据集（20 分，测试集 2 - 隐藏）

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

翻译由 GPT4.1 完成。