#PU1043. USACO 2020 US Open Contest, Gold — Problem 3. Exercise

    ID: 1608 传统题 文件IO:exercise 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open20来源:usaco.orgscoring:equal_test_cases模拟数学

USACO 2020 US Open Contest, Gold — Problem 3. Exercise

USACO 2020 US Open Contest, Gold — Problem 3. Exercise

题目描述

Farmer John has come up with a new morning exercise routine for the cows (again)! As before, Farmer John's NN cows (1≤N≤1041\le N\le 10^4) are standing in a line. The ii-th cow from the left has label ii for each 1≤i≤N1\le i\le N. He tells them to repeat the following step until the cows are in the same order as when they started. Given a permutation AA of length NN, the cows change their order such that the ii-th cow from the left before the change is AiA_i-th from the left after the change. For example, if A=(1,2,3,4,5)A=(1,2,3,4,5) then the cows perform one step. If A=(2,3,1,5,4)A=(2,3,1,5,4), then the cows perform six steps. The order of the cows from left to right after each step is as follows: 0 steps: (1,2,3,4,5)(1,2,3,4,5) 1 step: (3,1,2,5,4)(3,1,2,5,4) 2 steps: (2,3,1,4,5)(2,3,1,4,5) 3 steps: (1,2,3,5,4)(1,2,3,5,4) 4 steps: (3,1,2,4,5)(3,1,2,4,5) 5 steps: (2,3,1,5,4)(2,3,1,5,4) 6 steps: (1,2,3,4,5)(1,2,3,4,5) Find the sum of all positive integers KK such that there exists a permutation of length NN that requires the cows to take exactly KK steps. As this number may be very large, output the answer modulo MM (108≤M≤109+710^8\le M\le 10^9+7, MM is prime).

输入格式

The first line contains NN and MM.

输出格式

A single integer.

数据范围

Test cases 2-5 satisfy N≤102N\le 10^2. Test cases 6-10 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

5 1000000007
21
There exist permutations that cause the cows to take $1$, $2$, $3$, $4$, $5$,
and $6$ steps. Thus, the answer is $1+2+3+4+5+6=21$.