레이팅 미적용설명
농부 존이 (또다시) 소들을 위한 새로운 아침 운동 루틴을 고안했다!
이전처럼 농부 존의 소 \(N\)마리(\(1\le N\le 10^4\))가 한 줄로 서 있다. 왼쪽에서 \(i\)번째 소는 각 \(1\le i\le N\)에 대해 번호 \(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\)은 소수)으로 나눈 나머지를 출력한다.
문제 제공: Benjamin Qi
제약
배점
- 테스트 케이스 2-5는 \(N\le 10^2\)을 만족한다.
- 테스트 케이스 6-10은 추가 제약이 없다.
문제 제공: Benjamin Qi
입력 형식
첫째 줄에 \(N\)과 \(M\)이 주어진다.
출력 형식
정수 하나를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
exercise.in · 출력을 쓸 파일 exercise.out예제 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\).
문제 정보
태그