버스 정류장 (큰 입력)

화성 제1도시에는 버스 정류장이 $N$개 있고, 모두 길이가 $N-1$ km인 하나의 직선 위에 서 있다. 시장은 일을 단순하게 하는 편이라 정류장에 왼쪽부터 1번부터 $N$번까지 번호를 붙였고, 인접한 두 정류장 사이를 정확히 1 km로 맞췄다.

이 도시는 버스도 $K$대 운행한다. 시장은 버스 운행표를 짜야 하는데, 짜는 방법이 몇 가지인지 알고 싶다. 이 수는 아주 커질 수 있다. 다행히 제약이 몇 가지 있다.

• 하루가 시작될 때 모든 버스는 앞쪽 $K$개 정류장에 한 대씩 서 있다.
• 버스는 왼쪽에서 오른쪽으로만 움직인다. 1번이 가장 왼쪽 정류장이다.
• 하루가 끝날 때 모든 버스는 뒤쪽 $K$개 정류장에 한 대씩 서 있어야 한다.
• 정류장마다 정확히 한 대의 버스가 정차한다.
• 한 버스가 연달아 정차하는 두 정류장 사이의 거리는 최대 $P$ km이다.

시장을 위해 운행표의 개수를 세어라. 운행표가 아주 많다는 나쁜 소식을 전하지 않으려면, 실제 개수를 30031로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에는 공백 하나로 구분한 세 정수 $N$, $K$, $P$가 주어진다.

제한

• $1 < T \le 30$
• $1 < P \le 10$
• $K < N$
• $1 < K \le P$
• $1 < N < 10^9$

각 테스트 케이스마다 Case #t: x 형식으로 한 줄을 출력한다. $t$는 1부터 시작하는 테스트 케이스 번호이고, $x$는 운행표의 개수를 30031로 나눈 나머지이다.

버스를 A, B, C처럼 이름 붙이자. A는 1번 정류장에서, B는 2번 정류장에서 출발한다.

$N = 10$, $K = 3$, $P = 3$이면 운행표는 딱 하나다. A는 1, 4, 7, 10에 정차한다. B는 2, 5, 8에 정차한다. C는 3, 6, 9에 정차한다.

$N = 5$, $K = 2$, $P = 3$이면 운행표는 세 가지다.

• A는 1, 3, 5에, B는 2, 4에 정차한다
• A는 1, 3, 4에, B는 2, 5에 정차한다
• A는 1, 4에, B는 2, 3, 5에 정차한다