CF2001E2.Deterministic Heap (Hard 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$）。

当且仅当上述操作的每一步选择都是唯一的，即任意时刻 $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}$，则称该二叉树为最大堆（max-heap）。

如果对该堆执行第一次和第二次 $\mathrm{pop}$ 操作时，$\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 50$）。接下来是每组测试数据的描述。

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

保证所有测试数据中 $n$ 的和不超过 $100$，所有测试数据中 $k$ 的和不超过 $500$。

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

对于第一个测试点，如果选择 $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$ 为 $1$；
• 由于 $a_{2v} < a_{2v + 1}$，选择 $2v + 1$ 作为 $x$，此时 $x = 3$；
• 将 $a_x$ 赋值给 $a_v$，此时 $a = [0, -1, 0]$；
• 将 $x$ 赋值给 $v$，此时 $v = 3$；
• $v$ 为叶子节点，将 $a_v$ 赋值为 $-1$，此时 $a = [0, -1, -1]$。

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

由 ChatGPT 4.1 翻译