你经营着一家拥有 $N$ 间客房的酒店，这些房间沿一条长走廊排列，编号从 $1$ 到 $N$。你的客人们都是大家庭，每个家庭在入住时都要求恰好两间相邻的客房。如果两间房的编号之差恰好为 $1$，则称这两间房是相邻的。

今天刚开始时，你的酒店是空的。你一直使用以下简单的策略来为客人分配房间：每当一个家庭到达时，你会考虑所有当前均为空闲的相邻房间对，从中等概率随机选择一对，并将这对房间分配给该家庭。新家庭会不断地一个接一个地到达，但一旦没有空闲的相邻房间对，你就会挂出“客满”（NO VACANCY）的牌子，不再分配任何房间。

给定一个特定的房间编号，求该房间在挂出“客满”牌子时已被占用的概率。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含两个数字：房间总数 $N$ 和我们感兴趣的房间编号 $K$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所求概率对 $10^9+7$ 取模的结果。该概率定义如下：将房间 $K$ 被占用的概率表示为不可约分数 $p/q$。数字 $y$ 必须满足模方程 $y \times q \equiv p \pmod{10^9+7}$，且 $0 \le y \le 10^9+6$。可以证明，在该问题的约束条件下，这样的 $y$ 总是存在且唯一确定的。

数据范围

$1 \le T \le 100$。 $1 \le K \le N$。

小数据集（测试集 1 - 可见） $2 \le N \le 10^4$。

大数据集（测试集 2 - 隐藏） $2 \le N \le 10^7$。

样例

样例输入 1

4
3 1
3 2
4 1
4 2

样例输出 1

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

说明

在样例 #3 中，有四间房，我们要求第一间房被占用的概率。当第一个家庭到达时，有 3 种可能的情况，每种情况的概率均为 $1/3$：占用房间 $1+2$、$2+3$ 或 $3+4$。在第一种情况下，第一间房已被占用，并将保持占用状态。在第二种情况下，第一间房空闲且无法再容纳更多家庭，因此它将保持空闲。最后，在第三种情况下，下一个到达的家庭一定会占用房间 $1+2$，因此第一间房将被占用。第一间房被占用的概率为 $2/3$，答案为 $666666672$，因为 $(666666672 \times 3) \pmod{1000000007} = 2 \pmod{1000000007}$。

样例 #1 的概率为 $1/2$，样例 #2 和 #4 的概率为 $1$。