CF2238F.Infinite Work

More monkeys!

— Exponential Idle

You are in charge of a large scientific project studying an unusual function. To carry it out, you hired $10^{10^{100}}$ students and numbered them with natural numbers from $1$ to $10^{10^{100}}$. The students form a hierarchy:

• Student $1$ is the main one.
• For any $i \geq 2$, the direct supervisor of student $i$ is student $\left\lfloor \frac{i}{2} \right\rfloor$.
• The direct subordinates of student $i$ are students $2i$ and $2i+1$ (if these numbers do not exceed $10^{10^{100}}$).
• Subordination is transitive: if $a$ is subordinate to $b$, and $b$ is subordinate to $c$, then $a$ is subordinate to $c$.

Initially, all students are working.

There are $n$ days left until the project is completed. Each day consists of two stages:

• Hiring. Each working student $i$ hires all the non-working students who are directly subordinate to him:
  • If student $2i$ is not working and $2i \leq 10^{10^{100}}$, he starts working.
  • If student $2i + 1$ is not working and $2i + 1 \leq 10^{10^{100}}$, he starts working.Newly hired students cannot hire anyone on the same day.
• Firing. You may choose any set of working students and directly fire each of them. If student $i$ is directly fired, then all of his subordinates are automatically fired as well. Such firings are called indirect. Student $1$ cannot be fired.

Additional restriction: Each student may be fired (directly or indirectly) at most once. If a previously fired student is hired again, it is forbidden to perform a firing that would cause this student to be fired again.

Below (showing only the first $15$ students) are examples of how to choose students for direct firing on each day so that after $2$ days exactly $5$ students remain. The number at the top corresponds to the student number, edges show subordination.

Students who are working and have not been fired are marked green, students who have been fired are marked white, and students who were previously fired but have been rehired are marked red.

Day $1$, before firing. All students are hired. Day $1$, after firing. Students $2$, $6$, $7$ are fired. Day $2$, before firing. Students $2$, $6$, $7$ are hired. Note that during the firing stage, student $3$ cannot be directly fired, as this would lead to firing students $6$ and $7$, who have already been fired before this moment.

Your goal is to make it so that exactly $n$ days later there are exactly $k$ working students left in the project. At the same time, you need to minimize the total number of direct firings over the whole period.

Find the number of ways to choose the students for direct firing on each day so that the final number of working students is $k$, and the total number of direct firings is minimal possible. Output the answer modulo $10^9 + 7$.

更多猴子！

——《指数空闲》

你负责一个大型科学研究项目，研究一种特殊的函数。为开展该项目，你雇佣了 $10^{10^{100}}$ 名学生，并用从 $1$ 到 $10^{10^{100}}$ 的自然数对他们进行编号。这些学生构成一个层级结构：

• 学生 $1$ 是总负责人；
• 对任意 $i \geq 2$，学生 $i$ 的直属上级是学生 $\left\lfloor \frac{i}{2} \right\rfloor$；
• 学生 $i$ 的直属下属是学生 $2i$ 和 $2i+1$（前提是这两个编号不超过 $10^{10^{100}}$）；
• 隶属关系具有传递性：若 $a$ 隶属于 $b$，且 $b$ 隶属于 $c$，则 $a$ 隶属于 $c$。

初始时，所有学生均处于工作状态。

距离项目完成还剩 $n$ 天。每一天包含两个阶段：

• 招聘阶段：每个正在工作的学生 $i$ 将招聘其所有尚未工作的直属下属：
  • 若学生 $2i$ 尚未工作，且 $2i \leq 10^{10^{100}}$，则他开始工作；
  • 若学生 $2i + 1$ 尚未工作，且 $2i + 1 \leq 10^{10^{100}}$，则他开始工作。
    当日新招聘的学生不能在同一天内再招聘他人。
• 解雇阶段：你可以任选一组正在工作的学生，直接解雇其中每一位。若学生 $i$ 被直接解雇，则其所有下属也将被自动解雇（此类解雇称为间接解雇）。学生 $1$ 不可被解雇。

附加限制：每位学生至多被解雇（直接或间接）一次。若某位先前已被解雇的学生被重新招聘，则禁止执行会导致该学生再次被解雇的任何解雇操作。

下图（仅展示前 $15$ 名学生）给出了一个示例：通过在每天选择适当的人员进行直接解雇，使得经过 $2$ 天后恰好剩余 $5$ 名学生。顶部数字表示学生编号，连线表示隶属关系。

正在工作且未被解雇的学生以绿色标记；已被解雇的学生以白色标记；此前曾被解雇但已被重新招聘的学生以红色标记。

第 $1$ 天，解雇前。所有学生均已招聘。
第 $1$ 天，解雇后。学生 $2$、$6$、$7$ 被解雇。
第 $2$ 天，解雇前。学生 $2$、$6$、$7$ 被重新招聘。注意：在解雇阶段，学生 $3$ 不可被直接解雇，因为这将导致学生 $6$ 和 $7$ 被解雇，而他们在此刻之前已被解雇过。

你的目标是：恰好经过 $n$ 天后，项目内恰好剩下 $k$ 名正在工作的学生。同时，你需要使整个期间内直接解雇的总人数最小。

请计算满足以下条件的方案数：每天选择哪些学生进行直接解雇，使得最终剩余的工作学生数恰好为 $k$，且直接解雇的总人数达到最小可能值。输出答案对 $10^9 + 7$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^9$, $1 \le k \le 2 \cdot 10^5$) — the number of days and the required final number of active students.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^9$，$1 \le k \le 2 \cdot 10^5$）——分别表示天数和所需的最终活跃学生人数。

For each test case, output one integer — the number of possible ways to choose firings on each day so that after $n$ days exactly $k$ students remain, under the condition that the total number of firings is minimal possible.

对于每个测试用例，输出一个整数——在满足总解雇人数最少的前提下，选择每天解雇方案的方法数，使得经过 $n$ 天后恰好剩下 $k$ 名学生。

In the first test case, there is $1$ way: on the first day, directly fire students numbered $2$ and $3$. Exactly one student, number $1$, remains.

In the second test case, there are $2$ possible ways:

• On the first day, directly fire students numbered $2$, $6$, and $7$. Students $1$ and $3$ remain. At the beginning of the second day, they hire students numbered $2$, $6$, and $7$.
• On the first day, directly fire students numbered $3$, $4$, and $5$. Students $1$ and $2$ remain. At the beginning of the second day, they hire students numbered $3$, $4$, and $5$.

It can be shown that it is impossible to end with $5$ students by firing fewer than three students.

In the third test case, there are $2$ possible ways:

• On the first day, directly fire student $3$. On the second day, student $1$ hires student $3$. We fire nobody. On the third day, student $3$ hires students $6$ and $7$. After that, directly fire student $2$. Thus, $4$ students remain: $1$, $3$, $6$, and $7$.
• On the first day, directly fire student $2$. On the second day, student $1$ hires student $2$. We fire nobody. On the third day, student $2$ hires students $4$ and $5$. After that, directly fire student $3$. Thus, $4$ students remain: $1$, $2$, $4$, and $5$.

It can be shown that it is impossible to end with $4$ students by directly firing fewer than two students.

在第一个测试用例中，有 $1$ 种方式：第一天直接解雇编号为 $2$ 和 $3$ 的学生。恰好剩下一学生，即编号为 $1$ 的学生。

在第二个测试用例中，有 $2$ 种可能的方式：

• 第一天直接解雇编号为 $2$、$6$ 和 $7$ 的学生。学生 $1$ 和 $3$ 剩余。第二天开始时，他们重新雇佣编号为 $2$、$6$ 和 $7$ 的学生。
• 第一天直接解雇编号为 $3$、$4$ 和 $5$ 的学生。学生 $1$ 和 $2$ 剩余。第二天开始时，他们重新雇佣编号为 $3$、$4$ 和 $5$ 的学生。

可以证明：若想最终剩下 $5$ 名学生，则直接解雇的学生人数不可能少于三人。

在第三个测试用例中，有 $2$ 种可能的方式：

• 第一天直接解雇学生 $3$；第二天，学生 $1$ 雇佣学生 $3$，不进行任何解雇；第三天，学生 $3$ 雇佣学生 $6$ 和 $7$；随后直接解雇学生 $2$。最终剩余 $4$ 名学生：$1$、$3$、$6$ 和 $7$。
• 第一天直接解雇学生 $2$；第二天，学生 $1$ 雇佣学生 $2$，不进行任何解雇；第三天，学生 $2$ 雇佣学生 $4$ 和 $5$；随后直接解雇学生 $3$。最终剩余 $4$ 名学生：$1$、$2$、$4$ 和 $5$。

可以证明：若想最终剩下 $4$ 名学生，则直接解雇的学生人数不可能少于两人。