CF2001E1.Deterministic Heap (Easy Version)

这是该问题的简单版本。两个版本的区别在于确定性最大堆的定义、时间限制以及 $n$ 和 $t$ 的约束。只有在两个版本都被解决的情况下，你才能进行 hack。

考虑一个大小为 $2^n - 1$ 的完美二叉树，节点编号从 $1$ 到 $2^n-1$，根节点为 $1$。对于每个顶点 $v$（$1 \le v \le 2^{n - 1} - 1$），顶点 $2v$ 是其左儿子，顶点 $2v + 1$ 是其右儿子。每个节点 $v$ 还被赋予一个值 $a_v$。

定义操作 $\mathrm{pop}$ 如下：

1. 初始化变量 $v$ 为 $1$；
2. 重复以下过程，直到顶点 $v$ 是叶子节点（即 $2^{n - 1} \le v \le 2^n - 1$）：
   1. 在 $v$ 的两个子节点中，选择值较大的那个，记为 $x$；如果它们的值相等（即 $a_{2v} = a_{2v + 1}$），你可以任选其一；
   2. 将 $a_x$ 赋值给 $a_v$（即 $a_v := a_x$）；
   3. 将 $x$ 赋值给 $v$（即 $v := x$）；
3. 将 $a_v$ 赋值为 $-1$（即 $a_v := -1$）。

当且仅当上述操作有唯一的执行方式时，我们称 $\mathrm{pop}$ 操作是确定性的。换句话说，只有在每次选择时 $a_{2v} \neq a_{2v + 1}$ 成立时，$\mathrm{pop}$ 操作才是确定性的。

如果对于每个顶点 $v$（$1 \le v \le 2^{n - 1} - 1$），都有 $a_v \ge a_{2v}$ 且 $a_v \ge a_{2v + 1}$，则称该二叉树为最大堆。

如果对该堆第一次执行 $\mathrm{pop}$ 操作时是确定性的，则称该最大堆为确定性最大堆。

初始时，每个顶点 $v$ 的 $a_v := 0$（$1 \le v \le 2^n - 1$），你的目标是统计通过恰好执行 $k$ 次如下操作 $\mathrm{add}$ 所能得到的不同确定性最大堆的数量：

• 选择一个整数 $v$（$1 \le v \le 2^n - 1$），并对从 $1$ 到 $v$ 的路径上的每个顶点 $x$，将 $a_x$ 加 $1$。

如果存在某个节点在两个堆中的值不同，则认为这两个堆是不同的。

由于答案可能很大，请输出对 $p$ 取模的结果。

每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 500$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n, k, p$（$1 \le n, k \le 500$，$10^8 \le p \le 10^9$，$p$ 为质数）。

保证所有测试用例中 $n$ 的和与 $k$ 的和不超过 $500$。

对于每个测试用例，输出一行一个整数，表示通过上述操作恰好 $k$ 次后能得到的不同确定性最大堆的数量，对 $p$ 取模。

对于第一个测试用例，只有一种方式生成 $a$，且该序列是确定性最大堆，所以答案是 $1$。

对于第二个测试用例，如果选择 $v = 1$ 并执行操作，则 $a = [1, 0, 0]$，由于 $a_2 = a_3$，在第一次执行 $\mathrm{pop}$ 操作时可以任选其一，因此该堆不是确定性最大堆。

如果选择 $v = 2$，则 $a = [1, 1, 0]$，第一次执行 $\mathrm{pop}$ 时，过程如下：

• 初始化 $v$ 为 $1$；
• 由于 $a_{2v} > a_{2v + 1}$，选择 $2v$ 作为 $x$，此时 $x = 2$；
• 将 $a_x$ 赋值给 $a_v$，此时 $a = [1, 1, 0]$；
• 将 $x$ 赋值给 $v$，此时 $v = 2$；
• 由于 $v$ 是叶子节点，将 $a_v$ 赋值为 $-1$，此时 $a = [1, -1, 0]$。

由于第一次 $\mathrm{pop}$ 操作是确定性的，所以这是一个确定性最大堆。同理，如果选择 $v = 3$，$a$ 也是确定性最大堆，因此答案是 $2$。

由 ChatGPT 4.1 翻译