← 返回题目列表

Codeforces · 2217/G

G. 向下枢轴

中文机器翻译题面 查看原题

考虑二叉树,其中每个节点最多有两个子节点,并且每个节点都标有 $$$0$$$ 或 $$$1$$$。

在一次操作中,您可以翻转通过根的任何简单路径上的所有标签。翻转标签意味着将 $$$0$$$ 更改为 $$$1$$$ 并将 $$$1$$$ 更改为 $$$0$$$。请注意,长度为 $$$1$$$ 且仅包含根的路径也是允许的。

的 树的 成本 这种二叉树的 被定义为使树中所有标签等于$$$0$$$所需的最少操作数。

给定两个整数 $$$n$$$ 和 $$$k$$$,计算具有精确 $$$n$$$ 节点且成本精确 $$$k$$$ 的不同标记二叉树的数量。由于答案可能非常大,因此输出它对 $$$10^9 + 7$$$ 取模。

如果两个二叉树具有不同的结构,或者它们具有相同的结构但至少有一个节点的标签不同,则认为它们是不同的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^6$$$, $$$0 \le k \le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,在新行中输出一个整数 - 具有 $$$n$$$ 节点和成本 $$$k$$$ 的标记二叉树的数量,以 $$$10^9+7$$$ 为模。

示例

输入
复制

6
2 0
2 1
1 1
7 6
69 67
314159 42

输出
复制

2
4
1
2016
382216284
559671824

注意

在第一个测试用例中,我们有 $$$n=2$$$ 和 $$$k=0$$$。有两种可能的树——带有左子节点的根和带有右子节点的根。由于我们需要 $$$0$$$ 的成本,因此所有节点都必须标记为 $$$0$$$。因此,答案是$$$2$$$。

在第二个测试用例中,$$$n=2$$$ 和 $$$k=1$$$。这样的树有$$$4$$$。有效的标记树如下图所示:

在第三个测试用例中,$$$n=1$$$ 和 $$$k=1$$$。只有一棵树 - 带有标签 $$$1$$$ 的单个根节点。因此,答案是$$$1$$$。