시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1536 MB 11 7 7 70.000%

문제

수열 $a_{1}, \cdots, a_{n}$의 inversion이란 $i < j, a_{i} > a_{j}$를 만족하는 순서쌍 $(i,j)$의 개수이다.

$1, \cdots, n$의 순열 중 inversion이 $k$개인 것의 개수를 $I(n, k)$라고 하자.

소수 $P = 10^{6} + 3$에 대해, $n, k$가 주어졌을 때 $I(n, k)$를 $P$로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

입력의 첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 $n, k$가 공백을 사이에 두고 주어진다.

출력

테스트 케이스마다 한 줄에 $I(n, k)$를 $P$로 나눈 나머지를 출력한다. $P = 10^{6} + 3$은 소수이다.

제한

  • $1 \le T \le 10$
  • $1 \le n \le 2 \times 10^{10}$
  • $0 \le k \le 2n$
  • $P = 10^{6} + 3$은 소수이다.

예제 입력 1

10
10 2
10 4
10 6
10 8
10 10
10 12
10 14
10 16
10 18
10 20

예제 출력 1

44
440
2298
8095
21670
47043
86054
135853
187959
230131

출처

Contest > IDTcup > 제 3회 IDTcup E번