P17399 [ICPC 2018 Shenyang R] Rainbow Graph

A graph without loops or multiple edges is known as a simple graph. A vertex-colouring is an assignment of colours to each vertex of a graph. A proper vertex-colouring is a vertex-colouring in which no edge connects two identically coloured vertices. A vertex-colouring with $n$ colours of an undirected simple graph is called an $n$-rainbow colouring if every colour appears once, and only once, on all the adjacent vertices of each vertex. Note that an $n$-rainbow colouring is not a proper colouring, since adjacent vertices may share the same colour. An undirected simple graph is called an $n$-rainbow graph if the graph can admit at least one legal $n$-rainbow colouring. Two $n$-rainbow graphs $G$ and $H$ are called isomorphic if, between the sets of vertices in $G$ and $H$, a bijective mapping $f : V(G) \to V(H)$ exists such that two vertices in $G$ are adjacent if and only if their images in $H$ are adjacent. Your task in this problem is to count the number of distinct non-isomorphic $n$-rainbow graphs having $2n$ vertices and report that number modulo a prime number $p$.

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $1000$. For each test case, the only line contains two integers $n$ and $p$ where $1 \le n \le 64$ , $n+1 \le p \le 2^{30}$ and $p$ is a prime. We guarantee that the numbers of test cases satisfying $n \ge 16$ , $n \ge 32$ and $n \ge 48$ are no larger than $200$, $100$ and $20$ respectively.

For each test case, output a line containing `"Case #x: y"` (without quotes), where $x$ is the test case number starting from $1$ , and $y$ is the answer modulo $p$.

If you came up with a solution such that the time complexity is asymptotic to $p(n)$, the number of partitions of $n$, or similar, you might want to know $p(16) = 231$, $p(32) = 8349$, $p(48) = 147273$ and $p(64) = 1741630$ . The following figures illustrate all the non-isomorphic rainbow graphs mentioned in the first four sample cases. :::align{center}  Figure 1: the non-isomorphic 1-rainbow graph with 2 vertices  Figure 2: the non-isomorphic 2-rainbow graph with 4 vertices  Figure 3: the non-isomorphic 3-rainbow graphs with 6 vertices  Figure 4: the non-isomorphic 4-rainbow graphs with 8 vertices :::