Problem 3. Exercise

USACO 2020 US Open Contest, Gold

Farmer John（又）想到了一个新的奶牛晨练方案！

如同之前，Farmer John 的 $N$ 头奶牛（$1\le N\le 10^4$）站成一排。对于 $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$ 是质数）。

输入格式（文件名：exercise.in）：

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

输出格式（文件名：exercise.out）：

输出一个整数。

输入样例：

5 1000000007

输出样例：

21

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

测试点性质： 测试点 2-5 满足 $N\le 10^2$。测试点 6-10 没有额外限制。

供题：Benjamin Qi