405423: GYM101955 H 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 $$$2 n$$$ 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$$$.

5
1 11059
2 729557
3 1461283
4 5299739
63 49121057

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: 3
Case #5: 5694570

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.