题目描述

不含自环或多重边的图称为简单图。

顶点着色是为图的每个顶点指定一种颜色。正常顶点着色是一种顶点着色，其中没有边连接两个颜色相同的顶点。

对一个无向简单图进行 $n$ 种颜色的顶点着色，如果对于每个顶点，其所有邻接顶点上每种颜色恰好出现一次，则称该着色为 $n$-彩虹着色。注意，$n$-彩虹着色不是正常着色，因为相邻顶点可能共享相同的颜色。

如果一个无向简单图能够容纳至少一种合法的 $n$-彩虹着色，则称该图为 $n$-彩虹图。两个 $n$-彩虹图 $G$ 和 $H$ 称为同构的，如果在 $G$ 和 $H$ 的顶点集合之间存在一个双射 $f : V(G) \to V(H)$，使得 $G$ 中两个顶点相邻当且仅当它们在 $H$ 中的像相邻。

本题的任务是计算具有 $2n$ 个顶点的不同构的 $n$-彩虹图的数量，并报告该数模一个素数 $p$ 的结果。

输入格式

输入包含多个测试用例，第一行包含一个正整数 $T$，表示测试用例的数量，最多不超过 $1000$。

对于每个测试用例，仅有一行包含两个整数 $n$ 和 $p$，其中 $1 \le n \le 64$，$n+1 \le p \le 2^{30}$，且 $p$ 为素数。

我们保证满足 $n \ge 16$、$n \ge 32$ 和 $n \ge 48$ 的测试用例数量分别不超过 $200$、$100$ 和 $20$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"（不含引号），其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是答案模 $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

提示

如果你的解法的时间复杂度与 $p(n)$（$n$ 的划分数）或类似量渐进相关，你或许想知道 $p(16) = 231$、$p(32) = 8349$、$p(48) = 147273$ 和 $p(64) = 1741630$。

下面的图展示了前四个样例中提到的所有不同构的彩虹图。

:::align{center}

图 1: 具有 2 个顶点的不同构的 1-彩虹图

图 2: 具有 4 个顶点的不同构的 2-彩虹图

图 3: 具有 6 个顶点的不同构的 3-彩虹图

图 4: 具有 8 个顶点的不同构的 4-彩虹图 :::

翻译由 DeepSeek V4 Pro 完成