人类社会学研究一群人之间的人际关系。我们可以将 $n$ 个人的关系抽象为一个无向图 $G = (V, E)$，其中有 $n$ 个顶点。当且仅当第 $i$ 个人和第 $j$ 个人是朋友时，边 $(i, j) \in E$。我们可以通过多种方式分析该图，并了解关于这群人的许多有趣事实。

本学期，Rikka 选修了人类社会学作为选修课，她的期末项目是研究关系图。你知道，如果你想获得更高的 GPA，最好在选修课上投入大量时间。因此，Rikka 在这门课上非常努力，她希望完成一个令人印象深刻的项目。

Rikka 对图中的“桥”很感兴趣。一个三元组 $(i, j, k)$，满足 $i < j$ 且 $k \notin \{i, j\}$，被称为一个“桥”，当且仅当 $(i, k) \in E$ 且 $(j, k) \in E$，但 $(i, j) \notin E$。通俗地说，对于一个“桥” $(i, j, k)$，人 $k$ 将成为 $i$ 和 $j$ 之间社交联系的桥梁。关系图中的“桥”越少，这群人就越稳定。

Rikka 想要研究她大学里的一个学生群体，该群体共有 $n$ 名学生。她想验证该群体是否足够稳定，即该群体中“桥”的数量是否小于或等于 $K$。Rikka 尚未研究学生之间的关系，但她想先做一个估计。由于存在 $2^{\binom{n}{2}}$ 种可能的关系图，她想计算其中稳定图的数量。由于这个数字可能非常大，因此必须将其对给定的数 $m$ 取模。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^3$)，表示测试用例的数量。

每个测试用例占一行，包含三个整数 $n, K, m$ ($1 \le n \le 10^3, 0 \le K \le 8, 10^8 \le m \le 10^9 + 7$)。

保证 $n > 100$ 的测试用例不超过 50 个。

输出格式

对于每个测试用例，输出一行，包含一个整数：稳定图的数量对 $m$ 取模的结果。

样例

输入 1

3
4 1 1000000007
4 2 1000000007
1000 8 1000000007

输出 1

27
57
509805471