{"raw_statement":[{"iden":"statement","content":"A graph without loops or multiple edges is known as a simple graph.\n\nA 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.\n\nA 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.\n\nAn 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) arrow.r V (H)$ exists such that two vertices in $G$ are adjacent if and only if their images in $H$ are adjacent.\n\nYour 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$.\n\nThe 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$.\n\nFor each test case, the only line contains two integers $n$ and $p$ where $1 <= n <= 64$, $n + 1 <= p <= 2^(30)$ and $p$ is a prime.\n\nWe guarantee that the numbers of test cases satisfying $n >= 16$, $n >= 32$ and $n >= 48$ are no larger than $200$, $100$ and $20$ respectively.\n\nFor 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$.\n\nIf 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$.\n\nThe following figures illustrate all the non-isomorphic rainbow graphs mentioned in the first four sample cases.\n\n"},{"iden":"input","content":"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 <= n <= 64$, $n + 1 <= p <= 2^(30)$ and $p$ is a prime.We guarantee that the numbers of test cases satisfying $n >= 16$, $n >= 32$ and $n >= 48$ are no larger than $200$, $100$ and $20$ respectively."},{"iden":"output","content":"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$."},{"iden":"note","content":"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.  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ p $ a prime.  \nAn **$ n $-rainbow graph** is a simple undirected graph $ G = (V, E) $ with $ |V| = 2n $, equipped with a vertex colouring $ c: V \\to \\{1, 2, \\dots, n\\} $ such that for every vertex $ v \\in V $, the multiset of colours of its neighbours is exactly $ \\{1, 2, \\dots, n\\} $, each appearing exactly once.  \n*(Note: Adjacent vertices may share the same colour; colouring is not proper.)*  \n\nTwo $ n $-rainbow graphs $ G, H $ are **isomorphic** if there exists a bijection $ f: V(G) \\to V(H) $ such that $ \\{u,v\\} \\in E(G) \\iff \\{f(u),f(v)\\} \\in E(H) $, and $ c_G(u) = c_H(f(u)) $ for all $ u \\in V(G) $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 64 $  \n2. $ n+1 \\le p \\le 2^{30} $, $ p $ prime  \n3. Number of test cases $ T \\le 1000 $, with at most 200 cases where $ n \\ge 16 $, 100 where $ n \\ge 32 $, 20 where $ n \\ge 48 $  \n\n**Objective**  \nFor each test case, compute the number of **non-isomorphic** $ n $-rainbow graphs on $ 2n $ vertices, modulo $ p $.","simple_statement":"Count the number of non-isomorphic n-rainbow graphs with 2n vertices, modulo prime p.","has_page_source":false}