E2. 确定性堆（困难版）
每个测试点的时间限制：4 秒
内存限制：512 兆字节

这是该问题的困难版。两个版本的区别在于确定性最大堆的定义、时间限制以及 $n$ 和 $k$ 的约束。只有当问题的两个版本都通过时，你才能进行 hack。

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

定义 pop 操作如下：

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

我们称这次 pop 操作是确定性的，如果整个操作过程只有唯一一种方式。换句话说，在需要选择子节点时，始终满足 $a_{2v} \neq a_{2v+1}$。

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

一个最大堆是确定性的，如果当我们第一次和第二次对该堆执行 pop 操作时，这些 pop 操作都是确定性的。

初始时，所有节点的值 $a_v := 0$（$1 \le v \le 2^n - 1$），你的目标是计算通过恰好执行 $k$ 次如下定义的 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$ 次 add 操作所能产生的不同确定性最大堆的数量，对 $p$ 取模。

---

示例

输入

6  
2 1 998244353  
3 2 998244853  
3 3 998244353  
3 4 100000037  
4 2 100000039  
4 3 100000037  

输出

2  
12  
40  
100  
32  
224  

输入

1  
100 500 100000037  

输出

66681128  

输入

2  
87 63 100000037  
13 437 100000039  

输出

83566569  
54517140  

---

说明
对于第一个测试用例：

• 如果选择 $v = 1$ 执行 add 操作，得到 $a = [1, 0, 0]$，由于 $a_2 = a_3$，第一次 pop 操作时可以选择任意一个子节点，因此该堆不是确定性最大堆。
• 如果选择 $v = 2$，得到 $a = [1, 1, 0]$：
  • 第一次 pop：
    • 初始 $v = 1$，$a_2 > a_3$，选择 $x = 2$，$a_1 := a_2 = 1$，$v := 2$，$a_2 := -1$ → $a = [1, -1, 0]$。
  • 第二次 pop：
    • 初始 $v = 1$，$a_2 < a_3$，选择 $x = 3$，$a_1 := a_3 = 0$，$v := 3$，$a_3 := -1$ → $a = [0, -1, -1]$。
  • 第一次和第二次 pop 都是确定性的，所以这是确定性最大堆。
• 同样，选择 $v = 3$ 也会得到一个确定性最大堆。
• 因此答案是 $2$。