::::info[引言：其之三]
:::align{center}
:::
::::
隙间的另一侧，既没有天空，也没有大地。
普通的魔法使骑着扫帚，如同流星一般从张开的隙间飞出。「拉普拉斯之眼」
在她身后一一闭合，最后的红光熄灭，隙间悄然合拢，在阴暗而无垠的空间中消失不见。
雾雨魔理沙用双手用力摁住扫帚，随即悬停在空旷的世界的中央。
——她的下方，有一扇由数字的光环围绕着的，紧闭的巨大「门扉」。
魔理沙迅速地认出了这扇来自「秘神」的禁忌之门。想必这正是秘神设下的机关，只要顺利通过，就能够窥探到异变背后的真相。
那么当下解决异变的关键一步，自然是找到这扇门的密码，打开它，然后前往它的背后——幕后黑手的巢穴。
魔理沙低头观察着光环上数字的跳跃与变幻。对于惯于搜刮遗迹与破解机关的魔法使而言，这样的挑战可是相当吸引人的。
「破译密码什么的，我魔理沙可擅长了 DA☆ZE。」
魔理沙抬起帽沿，开始认真观察这片地下迷径的运作规律。
原始题面
光环上写有 个数字，围绕着中央的门扉形成一个圆圈。魔理沙按顺序给每一个位置编了号，分别为 。最开始， 号位置上写了一个数字 ，且 是一个 的排列。
最开始光环上显示的数字就是门扉的密码。然而数字的排列在接下来的 秒内发生了变化：在第 秒，圆环上的第 个位置亮起，它两侧的数字发生了交换。
魔理沙观察到，存在某一次交换，交换的两个数一个小于它们中间的数，一个大于它们中间的数。
借助这一条信息，魔理沙想知道这扇门有多少种可能的密码。
由于答案可能过大，魔理沙会告诉你一个大质数 ，让你回答答案对 取模的结果。
形式化题意
一个环上有 个点，编号分别为 ，其中 与 相邻， 与 相邻。
每个点上有一个数字，点 上的数字是 ，其中 为 的一个排列。
依次对于 ，交换与点 相邻的两个点上的数字。
现在给定整数 ，求有多少个 的排列 满足，在进行上述交换操作的过程中：
- 存在正整数 ，设第 次操作交换的两个点上的数字是 ，则有 （此处的 指交换操作过程中点 上的数字）。
答案对质数 取模。
