레이팅 미적용설명
\(1\) 이상 \(N\) 이하의 각 정수가 정확히 한 번씩 나타나는 \(N\)개의 정수로 이루어진 수열을 생각하자.
수열에서 앞에 오는 수가 뒤에 오는 수보다 크면 그 두 수의 쌍이 혼란스럽다고 한다.
수열의 혼란도는 수열에 있는 혼란스러운 쌍의 개수이다. 예를 들어 수열 \(3\ 2\ 1\)의 혼란도는 \(3\)인데, 혼란스러운 쌍이 \((3, 2)\), \((3, 1)\), \((2, 1)\)의 \(3\)개이기 때문이다.
혼란도가 정확히 \(C\)인 길이 \(N\)의 수열의 개수를 계산하는 프로그램을 작성하시오.
제약
입력 형식
입력의 첫째 줄이자 유일한 줄에 두 정수 \(N\) (\(1 \le N \le 1000\))과 \(C\) (\(0 \le C \le 1000000000\))가 주어진다.
출력 형식
수열의 개수를 \(1000000000\)으로 나눈 나머지를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 60점 |
예제 1
입력
10 1출력
9예제 2
입력
4 3출력
6예제 3
입력
9 13출력
17957문제 정보
태그