Exercise

题目描述

农夫约翰为奶牛们想出了一个新的晨练流程（又来了）！

和之前一样，农夫约翰的 $N$ 头奶牛（$1\le N\le 10^4$）排成一列站着。从左到右第 $i$ 头奶牛的编号为 $i$，其中 $1\le i\le N$。他让它们重复执行如下步骤，直到奶牛们回到开始时的相同顺序。

给定一个长度为 $N$ 的排列 $A$，奶牛们改变队列顺序，使得变化前从左到右第 $i$ 头奶牛，在变化后从左到右位于第 $A_i$ 个位置。

例如，若 $A=(1,2,3,4,5)$，则奶牛们执行一步。若 $A=(2,3,1,5,4)$，则奶牛们执行六步。每一步之后奶牛从左到右的顺序如下： 0 steps: $(1,2,3,4,5)$ 1 step: $(3,1,2,5,4)$ 2 steps: $(2,3,1,4,5)$ 3 steps: $(1,2,3,5,4)$ 4 steps: $(3,1,2,4,5)$ 5 steps: $(2,3,1,5,4)$ 6 steps: $(1,2,3,4,5)$

求所有正整数 $K$ 的和，使得存在一个长度为 $N$ 的排列，能让奶牛们恰好用 $K$ 步回到初始顺序。

由于该数可能非常大，请输出答案对 $M$ 取模后的结果（$10^8\le M\le 10^9+7$，且 $M$ 为质数）。

输入格式

第一行包含 $N$ 和 $M$。

输出格式

输出一个整数。

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

标签: USACO|2020|Gold

来源

USACO|2020|Gold