버스 정류장 (작은 입력)

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

도시에는 버스가 $K$대 있다. 시장은 하루치 운행 계획을 몇 가지로 세울 수 있는지 알고 싶다. 계획은 다음 조건을 모두 지켜야 한다.

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

버스의 운행 경로는 그 버스가 정차하는 정류장을 번호가 커지는 순서로 늘어놓은 것이다. 어떤 정류장에 정차하는 버스가 다르면 두 계획은 서로 다른 계획이다. 계획의 수가 매우 커질 수 있으므로 30031로 나눈 나머지를 출력한다.

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

제한

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

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

$N = 10$, $K = 3$, $P = 3$이면 계획이 하나뿐이다. 버스를 A, B, C라고 하면 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번