3200 - 奶牛晨练

Farmer John(又)想到了一个新的奶牛晨练方案!
如同之前,Farmer John 的 N 头奶牛站成一排。对于 1\le i\le N 的每一个 i,从左往右第 i 头奶牛的编号为 i。他告诉她们重复以下步骤,直到奶牛们与她们开始时的顺序相同。

给定长为 N 的一个排列 A,奶牛们改变她们的顺序,使得在改变之前从左往右第 i 头奶牛在改变之后为从左往右第 A_i 头。
例如,如果一开始A=(1,2,3,4,5),每一步使得原本在位置1的奶牛移动到位置2;位置2的奶牛移动到位置3;位置3的奶牛移动到位置1,位置4的奶牛移动到位置5,位置5的奶牛移动到位置4。那么奶牛们移动一次后的位置是A=(3,1,2,5,4)。那么奶牛们总共进行六步就能回到初始的状态。每步之后奶牛们从左往右的顺序如下:

0 步:(1,2,3,4,5)
1 步:(3,1,2,5,4)
2 步:(2,3,1,4,5)
3 步:(1,2,3,5,4)
4 步:(3,1,2,4,5)
5 步:(2,3,1,5,4)
6 步:(1,2,3,4,5)
求所有正整数 K 的和,使得存在一个长为 N 的排列,奶牛们需要进行恰好 K 步。

由于这个数字可能非常大,输出答案模 M 的余数(10^8\le M\le 10^9+7M 是质数)。

输入

输入的第一行包含 NM

输出

样例

输入

5 1000000007

输出

21

提示

存在排列使得奶牛需要进行 12345 以及 6 步。因此,答案为 1+2+3+4+5+6=21

对于 100\% 的数据,1\le N\le 10^4

来源

USCAO

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题