[USACO20OPEN]Exercise G

题目描述

Farmer John(又)想到了一个新的奶牛晨练方案! 如同之前,Farmer John 的 $N$ 头奶牛站成一排。对于 $1\le i\le N$ 的每一个 $i$,从左往右第 $i$ 头奶牛的编号为 $i$。他告诉她们重复以下步骤,直到奶牛们与她们开始时的顺序相同。 给定长为 $N$ 的一个排列 $A$,奶牛们改变她们的顺序,使得在改变之前从左往右第 $i$ 头奶牛在改变之后为从左往右第 $A_i$ 头。 例如,如果 $A=(1,2,3,4,5)$,那么奶牛们总共进行一步。如果 $A=(2,3,1,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+7$,$M$ 是质数)。

输入输出格式

输入格式


输入的第一行包含 $N$ 和 $M$。

输出格式


输出一个整数。

输入输出样例

输入样例 #1

5 1000000007

输出样例 #1

21

说明

#### 样例解释: 存在排列使得奶牛需要进行 $1$、$2$、$3$、$4$、$5$ 以及 $6$ 步。因此,答案为 $1+2+3+4+5+6=21$。 ----- 对于 $100\%$ 的数据,$1\le N\le 10^4$。 共 $10$ 个测试点,其中 $1$ 为样例,其余性质如下: 测试点 $2\sim 5$ 满足 $N\le 10^2$。 测试点 $6\sim 10$ 没有额外限制。 ----- 出题人:Benjamin Qi