Inversion Statistics

문제

수열 $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$ 은 소수이다.

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

44
440
2298
8095
21670
47043
86054
135853
187959
230131

출처

• 문제를 만든 사람: TAMREF

• 문제를 검수한 사람: 79brue, aeren, qwerasdfzxcl