Counting Good Connections

In this problem we consider a labeled undirected simple connected graph (G=(V,E)) on (n) vertices (with labels (1,2,\dots,n)). In addition, you are given an integer (t) which is either 0 or 1. If (t=0) then the graph is further required to be a tree (i.e. there is a unique simple path between any two vertices). If (t=1) there is no extra restriction (other than connectivity).

We call a non–empty subset (W\subseteq V) with (|W|\ge2) \ntight if the induced subgraph on (W) is connected and for every two vertices (u,v\in W) the distance (i.e. the number of edges in a shortest path) satisfies (\mathrm{dis}(u,v)\le2).

A connected graph (G) is said to be a good connection if and only if there is exactly one way to partition (V) into several disjoint subsets (W_1,W_2,\dots,W_k) (with (k\ge1)) so that each (W_i) is tight (note that a valid partition must cover all vertices and each part must have size at least 2).

Kisaki wants to know, for the given (n) and (t), how many good connection ways are there if one only considers graphs meeting the description. Since the answer might be huge, output it modulo an (arbitrary) modulus (P) ((P) is not necessarily prime).

It turns out that (perhaps surprisingly) the only graphs that yield a unique tight‐partition are exactly certain trees. In particular, one may prove that if a tree is a good connection then either the whole vertex set (V) is tight (which happens exactly when the tree is a star) or (V) can be partitioned into pairs (which forces (n) to be even and the tree to have a unique perfect matching). One may show that therefore the answer is given by

(\text{ans}=\begin{cases}\n;1 & \text{if } n=2,\ ;n & \text{if } n\ge3 \text{ is odd,}\ ;{n\choose n/2},(n/2)!,(n/2)^{ (n/2)-2 } & \text{if } n\ge4 \text{ is even.}\n\end{cases})

You are to compute the answer modulo (P). (Note that for (t=1) the extra edges will always introduce extra partitions, so the good graphs under both (t=0) and (t=1) are exactly the good trees.)

inputFormat

The input begins with a single integer (Q) ((1\le Q\le 100)) denoting the number of queries. Each of the following (Q) lines contains three integers (n), (t) and (P) separated by spaces. (n) ((2\le n\le 50)) is the number of vertices, (t) is either 0 or 1, and (P) ((1\le P\le 10^9)) is the modulus.

outputFormat

For each query, output a single integer: the number of good connections modulo (P).

sample

3
2 0 100
3 1 100
4 0 1000

1
3
12