P16351 「Gensokyo OI Round 1」秘神之钥

::::info[引言：其之三] :::align{center} $\textbf{启禁忌之\color{green}门扉}\textbf{，窥探真相。}$ ::: :::: 隙间的另一侧，既没有天空，也没有大地。 普通的魔法使骑着扫帚，如同流星一般从张开的隙间飞出。「拉普拉斯之眼」 在她身后一一闭合，最后的红光熄灭，隙间悄然合拢，在阴暗而无垠的空间中消失不见。 雾雨魔理沙用双手用力摁住扫帚，随即悬停在空旷的世界的中央。 ——她的下方，有一扇由数字的光环围绕着的，紧闭的巨大「门扉」。 魔理沙迅速地认出了这扇来自「秘神」的禁忌之门。想必这正是秘神设下的机关，只要顺利通过，就能够窥探到异变背后的真相。 那么当下解决异变的关键一步，自然是找到这扇门的密码，打开它，然后前往它的背后——幕后黑手的巢穴。 魔理沙低头观察着光环上数字的跳跃与变幻。对于惯于搜刮遗迹与破解机关的魔法使而言，这样的挑战可是相当吸引人的。 「破译密码什么的，我魔理沙可擅长了 DA☆ZE。」 魔理沙抬起帽沿，开始认真观察这片地下迷径的运作规律。

#### 原始题面 光环上写有 $n$ 个数字，围绕着中央的门扉形成一个圆圈。魔理沙按顺序给每一个位置编了号，分别为 $1,2,\dots,n$。最开始，$i$ 号位置上写了一个数字 $a_i$，且 $a_1,\dots,a_n$ 是一个 $1 \sim n$ 的排列。 最开始光环上显示的数字就是门扉的密码。然而数字的排列在接下来的 $n$ 秒内发生了变化：在第 $i$ 秒，圆环上的第 $i$ 个位置亮起，它两侧的数字发生了交换。 魔理沙观察到，**存在**某一次交换，交换的两个数**一个小于它们中间的数，一个大于它们中间的数**。 借助这一条信息，魔理沙想知道这扇门有多少种可能的密码。 由于答案可能过大，魔理沙会告诉你一个大质数 $M$，让你回答答案对 $M$ 取模的结果。 #### 形式化题意 一个环上有 $n$ 个点，编号分别为 $1,2,\dots,n$，其中 $i$ 与 $i+1$ 相邻，$n$ 与 $1$ 相邻。 每个点上有一个数字，点 $i$ 上的数字是 $p_i$，其中 $\{p_i\}$ 为 $1 \sim n$ 的一个排列。 依次对于 $i = 1,2,\dots,n$，交换与点 $i$ 相邻的两个点上的数字。 现在给定整数 $n,M$，求有多少个 $1 \sim n$ 的排列 $\{p_i\}$ 满足，在进行上述交换操作的过程中： - **存在**正整数 $i \in \{1,2,\dots,n\}$，设第 $i$ 次操作交换的两个点上的数字是 $a,b (a < b)$，则有 $a < p_i < b$（此处的 $p_i$ 指交换操作过程中点 $i$ 上的数字）。 答案对质数 $M$ 取模。

**本题有多组测试数据。** 第一行一个整数 $T$，表示测试数据组数。 接下来 $T$ 行，每行两个整数 $n,M$，分别表示环上点数量和答案取模质数。

$T$ 行，每行一个整数，表示答案。

### 样例解释 #### 样例 #1 解释 以下是 $n=4$ 时符合要求的 $14$ 种排列： - $(1,2,4,3)$； - $(1,3,4,2)$； - $(1,4,3,2)$； - $(2,1,3,4)$； - $(2,1,4,3)$； - $(2,3,4,1)$； - $(2,4,3,1)$； - $(3,1,2,4)$； - $(3,2,1,4)$； - $(3,4,1,2)$； - $(3,4,2,1)$； - $(4,1,2,3)$； - $(4,2,1,3)$； - $(4,3,1,2)$。 ### 数据范围 本题**不采用**捆绑测试。 |测试点编号|$n \le$|特殊性质| |:---:|:-----:|:--:| | $1$ | $10$ | $T \le 10$ | | $2$ | $20$ | 无 | | $3$ | $100$ | 无 | | $4$ | $1000$ | 无 | | $5 \sim 6$ | $2 \times 10^4$ | 无 | | $7$ | $10^6$ | $n$ 为奇数 | | $8$ | $10^6$ | $n$ 为偶数 | | $9 \sim 10$ | $10^6$ | 无 | 此外，对于所有数据，$1 \le T \le 20, 3 \le n \le 10^6, 10^8 \le M < 10^9$，$M$ 是质数。