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

힌트