您负责一个研究不寻常函数的大型科学项目。为了实现这一目标,您雇佣了 $$$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$$$ 取模的答案。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — 天数和所需的最终活跃学生人数。
输出
对于每个测试用例,输出一个整数 - 每天选择解雇的可能方法的数量,以便在解雇总数尽可能少的情况下,在 $$$n$$$ 天后,恰好有 $$$k$$$ 学生留下来。
示例
输入复制
61 12 53 41 520 141000000000 20
输出复制
1224212012
注意
第一个测试用例中,有$$$1$$$方式:第一天,直接解雇编号为$$$2$$$和$$$3$$$的学生。只剩下一名学生,编号为 $$$1$$$。
在第二个测试用例中,有 $$$2$$$ 可能的方法:
- 第一天,直接解雇了编号为$$$2$$$、$$$6$$$、$$$7$$$的学生。学生 $$$1$$$ 和 $$$3$$$ 留下。第二天一开始,他们就雇用了编号为 $$$2$$$、$$$6$$$ 和 $$$7$$$ 的学生。
- 第一天,直接解雇了编号为$$$3$$$、$$$4$$$、$$$5$$$的学生。学生 $$$1$$$ 和 $$$2$$$ 留下。第二天一开始,他们就雇用了编号为 $$$3$$$、$$$4$$$ 和 $$$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$$$。