1853: [NewOJ Week 13] 错排旋转

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:4 通过:0

题目描述

错位排列:一个1-n的排列p,同时满足p[i]≠i。
序列a[1],a[2],...,a[n]的关于偏移量等于k旋转表示:将序列变成a[k],a[k+1],...,a[n],a[1],a[2],...,a[k-1]。
长度为n的序列存在n个不同的旋转。
给定一个错位排列D,f(D)表示存在多少个不同的旋转,使得旋转后的结果也是错位排列。
例如f([2,1])=1,[2,1]只存在1种旋转是错位排列。
f([3,1,2])=2,[3,1,2]只存在2种旋转是错位排列,分别是[3,1,2],[2,3,1]。
现在给定n和一个素数p,计算有多少个1-n的错位排列D满足f(D)=(n-2),由于答案过大,需要对p进行取模。

输入格式

输入两个数字n和p,3≤n≤1000000,10^8≤p≤10^9+7。
n表示排列长度,p为素数。

输出格式

输出一个数字表示答案。

输入样例 复制

样例1:
3 1000000007

样例2:
6 999999937

输出样例 复制

样例1:
0

样例2:
20