P17870 [FJCPC 2026] 变幻自在

如果无向图 $G$ 中没有重边与自环，则称 $G$ 是一张**简单无向图**。 对于无向图 $G$ 中任意一个点 $u$，与 $u$ 相连的边的条数称为 $u$ 的**度数**。 对于一张有 $n$ 个点的图 $G$，如果 $G$ 中的每个点都有其编号，并且编号构成 $1 \sim n$ 的排列，则称 $G$ 是一张**带标号图**。 如果带标号简单无向图 $G$ 中每个点的度数的奇偶性均相同，则称 $G$ 是一张**好图**。 给定正整数 $n$，请你求出恰好包含 $n$ 个点的好图的数量。由于答案可能很大，你只需要输出答案对给定整数 $m$ 取模的结果。 对于两张有 $n$ 个点的好图 $G_1, G_2$，如果存在 $1\leq u < v\leq n$ 使得其中一张图包含边 $(u, v)$ 而另一张图不包含边 $(u, v)$，则认为 $G_1, G_2$ 是不同的。

**本题测试点包含多组数据。** 第一行，一个正整数 $T$（$1\leq T\leq 10^4$），表示数据组数。 对于每组数据：一行，两个正整数 $n, m$（$1\leq n\leq 10^9$，$1\leq m\leq 10^9$），分别表示图的点数和模数。

对于每组数据，输出一行，一个整数，表示恰好包含 $n$ 个点的好图的数量对 $m$ 取模的结果。

对于 $n=1$，图中仅有点 $1$，无法连边。此时这张图是好图，答案为 $1$。 对于 $n=2$，无论图中有没有边连接点 $1$ 与点 $2$，得到的图都是好图。因此答案为 $2$。