버스 정류장

화성의 첫 번째 도시에는 N개의 버스 정류장이 있으며, 모두 길이가 N-1킬로미터인 직선 위에 나란히 놓여 있다. 시장은 일을 단순하게 처리하는 것을 좋아해서 버스 정류장에 1부터 N까지 번호를 부여하고, 인접한 정류장 사이의 거리를 정확히 1킬로미터로 정했다.

도시에는 K대의 버스도 있다. 시장은 버스 운행 일정을 계획해야 하며, 이를 몇 가지 방법으로 할 수 있는지 알고 싶어 한다. 이 수는 매우 클 수 있다. 다행히 몇 가지 제약 조건이 있다.

• 하루가 시작될 때 모든 버스는 처음 K개의 버스 정류장에 있다(정류장마다 버스 한 대)

• 버스는 왼쪽에서 오른쪽으로만 이동한다(1은 가장 왼쪽의 버스 정류장이다)

• 하루가 끝날 때 모든 버스는 마지막 K개의 버스 정류장에 있어야 한다(정류장마다 버스 한 대)

• 각 버스 정류장에는 정확히 한 대의 버스가 정차해야 한다

• 같은 버스가 연속해서 정차하는 임의의 두 정류장 사이의 거리는 최대 P킬로미터이다

시장이 운행 일정의 수를 계산할 수 있도록 도와주자. 하지만 그에게 아주 나쁜 소식(매우 많은 운행 일정)을 전하지 않도록, 실제 수를 30031로 나눈 나머지만 출력한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 < T ≤ 30 1 < P ≤ 10 K < N 1 < K ≤ P

작은 데이터 세트(테스트 세트 1 - 공개)

1 < N < 1000

큰 데이터 세트(테스트 세트 2 - 비공개)

1 < N < $10^{9}$

입력 파일의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 각 줄에는 공백 하나로 구분된 3개의 정수 N, K, P가 주어진다.

각 테스트 케이스마다 버스 운행 일정을 계획하는 방법의 수를(30031로 나눈 나머지) "Case #t: $[number of ways modulo 30031]$" 형식으로 출력한다. 여기서 t는 1부터 시작하는 테스트 케이스의 번호이다.

버스의 이름을 A, B, C...라고 하자. 첫 번째 테스트 케이스에서는 운행 일정을 계획하는 방법이 하나뿐이다: A → 1, 4, 7, 10. B → 2, 5, 8. C → 3, 6, 9. 두 번째 테스트 케이스에서 가능한 운행 계획은 다음과 같다: (A → 1,3,5. B → 2,4), (A → 1,3,4. B → 2,5), (A → 1,4. B → 2,3,5).