考虑二叉树,其中每个节点最多有两个子节点,并且每个节点都标有 $$$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$$$ 为模。
示例
输入复制
62 02 11 17 669 67314159 42
输出复制
2412016382216284559671824
注意
在第一个测试用例中,我们有 $$$n=2$$$ 和 $$$k=0$$$。有两种可能的树——带有左子节点的根和带有右子节点的根。由于我们需要 $$$0$$$ 的成本,因此所有节点都必须标记为 $$$0$$$。因此,答案是$$$2$$$。
在第二个测试用例中,$$$n=2$$$ 和 $$$k=1$$$。这样的树有$$$4$$$。有效的标记树如下图所示:
在第三个测试用例中,$$$n=1$$$ 和 $$$k=1$$$。只有一棵树 - 带有标签 $$$1$$$ 的单个根节点。因此,答案是$$$1$$$。