CF2217G Down the Pivot

考虑二叉树，每个节点最多有两个子节点，并且每个节点的标记是 $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$ 取模。

在第一个测试用例中，$n=2$，$k=0$。有两种可能的二叉树：一个根节点有一个左孩子，或一个根节点有一个右孩子。由于要求代价为 $0$，则所有节点都必须标记为 $0$，所以答案为 $2$。 在第二个测试用例中，$n=2$，$k=1$。这样的树一共有 $4$ 种。所有合法的带标记二叉树如下图所示：  在第三个测试用例中，$n=1$，$k=1$。只有一棵树，即单个根节点，标记为 $1$，所以答案为 $1$。 由 ChatGPT 5 翻译