Rikka with Bridges

Anthropoid sociology studies the interpersonal relationship of a group of people. We can abstract the relationship among $n$ people as an undirected graph $G=\langle V,E \rangle$ of size $n$. $(i,j) \in E$ if and only if the $i$th person and the $j$th person are friends. We can do a lot of analyses of this graph and can get a lot of interesting facts about this human group.

This semester, Rikka chooses an elective course about anthropoid sociology, and her final project is about the relationship graph. You know, if you want to get a higher GPA, you would better put a lot of time in the elective courses. So, Rikka works hard in this class, and she wants to finish an impressive project.

Rikka is interested in the "bridges" in the graph. A tuple $(i,j,k)(i <j, k \notin\{i,j\})$ is a bridge if and only if $(i,k),(j,k) \in E$ and $(i,j) \notin E$. For bridge $(i,j,k)$, $k$ will be the bridge of the social contacts between $i$ and $j$. The fewer bridges are inside the relationship graph, the more stable the human group will be.

Rikka wants to study a student group in her college which has $n$ students in it. She wants to verify whether the group is stable enough, i.e., whether the number of bridges in this group is less than or equal to $K$. Rikka has not researched the relationships among the students yet. But she wants to estimate the result at first. Since there are $2^{\binom{n}{2}}$ possible relationship graphs, she wants to calculate the number of stable graphs among them.

The first line contains a single integer $t(1 \leq t \leq 10^3)$, the numebr of testcases.

For each testcase, the first line contains three numbers $n,K,m(1 \leq n \leq 10^3, 0\leq K \leq 8,10^8 \leq m \leq 10^9+7)$.

The input gurantees that there are at most $50$ testcases with $n > 100$

For each testcase, output a single line with a single number, the answer modulo $m$.

3
4 1 1000000007
4 2 1000000007
1000 8 1000000007

27
57
509805471

寒武纪ACM金牌训练营-重现赛