CF2238F Infinite Work

更多的猴子！ —— Exponential Idle 你负责一个大型科学项目，研究一个不寻常的函数。为此你雇佣了 $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$ 号学生）为每一天如何选择直接解雇哪些学生的示例，使得两天后正好剩余 $5$ 名学生。顶端数字为学生编号，连线表示从属关系。 绿色为仍在工作且未被解雇的学生，白色为已被解雇，红色为曾被解雇但已重新招回工作的学生。  第 $1$ 天，解雇前。所有学生都工作。  第 $1$ 天，解雇后。解雇了 $2$、$6$、$7$ 号学生。  第 $2$ 天，解雇前。$2$、$6$、$7$ 号被重新招回。注意解雇阶段不能直接解雇 $3$ 号，因为那样会再次解雇 $6$ 和 $7$ 号，这违反条件。 你的目标是在经过恰好 $n$ 天后，使得项目中正好剩下 $k$ 个在岗的学生，并使这期间直接解雇的总人数尽可能少。 请计算有多少种不同的每天直接解雇方式，可以在 $n$ 天后正好剩下 $k$ 个学生，并且直接解雇人数总数最少。请将答案对 $10^9 + 7$ 取模后输出。

每组测试含有多组数据。第一行为测试组数 $t$（$1 \leq t \leq 10^5$）。 接下来每组数据一行，包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^9$，$1 \leq k \leq 2 \cdot 10^5$），分别表示剩余天数和最终需要的在岗学生数。

对于每组测试，输出一个整数，表示满足要求的直接解雇方式数（最小直接解雇人数的情况下）。答案对 $10^9+7$ 取模。

对于第一组样例，只有一种方案：第一天直接解雇 $2$ 号和 $3$ 号学生，最后只剩下 $1$ 号学生。 对于第二组样例，有 $2$ 种方案： - 第一天直接解雇 $2$、$6$ 和 $7$ 号。最终剩下 $1$ 和 $3$ 号。第二天初他们又招回了 $2$、$6$ 和 $7$ 号。 - 第一天直接解雇 $3$、$4$、$5$ 号。最终剩下 $1$ 和 $2$ 号。第二天初他们又招回了 $3$、$4$、$5$ 号。 可以证明，若解雇人数少于 $3$ 人不可能最后剩下 $5$ 个学生。 对于第三组样例，也有 $2$ 种方案： - 第一天解雇 $3$ 号。第二天 $1$ 号重新招回 $3$ 号，没人解雇。第三天 $3$ 号招回 $6$、$7$ 号，然后直接解雇 $2$ 号。最终剩下 $1$、$3$、$6$、$7$ 号。 - 第一天解雇 $2$ 号。第二天 $1$ 号重新招回 $2$ 号，没人解雇。第三天 $2$ 号招回 $4$、$5$ 号，然后直接解雇 $3$ 号。最终剩下 $1$、$2$、$4$、$5$ 号。 可以证明，若直接解雇人数少于 $2$ 人，最后不可能剩下 $4$ 个学生。 由 ChatGPT 5 翻译