Tại Thành phố Thứ nhất của Sao Hỏa có \(N\) trạm xe buýt, tất cả được sắp xếp trên một đường thẳng có chiều dài \(N-1\) km. Thị trưởng thích mọi thứ đơn giản, vì vậy ông đã đánh số các trạm xe buýt từ \(1\) đến \(N\), và các trạm liền kề cách nhau đúng \(1\) km.

Cũng có \(K\) chiếc xe buýt trong thành phố. Thị trưởng phải lập kế hoạch lịch trình xe buýt và ông muốn biết có bao nhiêu cách để thực hiện điều đó. Con số này có thể rất lớn. May mắn thay, có một vài ràng buộc:

• Vào đầu ngày, tất cả các xe buýt đều ở \(K\) trạm xe buýt đầu tiên (mỗi trạm một xe).
• Các xe buýt chỉ di chuyển từ trái sang phải (trạm \(1\) là trạm ngoài cùng bên trái).
• Vào cuối ngày, tất cả các xe buýt phải ở \(K\) trạm xe buýt cuối cùng (mỗi trạm một xe).
• Tại mỗi trạm xe buýt, chính xác một xe buýt phải dừng lại.
• Đối với cùng một xe buýt, khoảng cách giữa hai điểm dừng liên tiếp bất kỳ tối đa là \(P\) km.

Hãy giúp thị trưởng đánh giá số lượng lịch trình. Tuy nhiên, đừng đưa cho ông ấy tin quá xấu (quá nhiều lịch trình), vì vậy chỉ cần xuất ra số lượng thực tế theo modulo \(30031\).

Dữ liệu vào

Dòng đầu tiên trong tệp đầu vào là số lượng bộ test \(T\).
Mỗi dòng trong \(T\) dòng tiếp theo chứa 3 số nguyên cách nhau bởi một khoảng trắng: \(N\), \(K\) và \(P\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra số cách lập kế hoạch lịch trình xe buýt (modulo \(30031\)) theo định dạng Case #t: [số cách modulo 30031] với t là số thứ tự của bộ test, bắt đầu từ 1.

Ràng buộc

• \(1 < T \le 30\)
• \(1 < P \le 10\)
• \(K < N\)
• \(1 < K \le P\)

Phân nhóm

• Small dataset (Test set 1): \(1 < N < 1000\)
• Large dataset (Test set 2): \(1 < N < 10^9\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
10 3 3
5 2 3
40 4 8

Case #1: 1
Case #2: 3
Case #3: 7380

Nguồn

Google Code Jam 2008, Vòng bán kết EMEA, bài Bus Stops.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.