역순서쌍 통계

수열 $a_1, \cdots, a_n$에서 $i < j$이고 $a_i > a_j$를 만족하는 순서쌍 $(i, j)$를 inversion이라고 한다. $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$은 소수이다.