Quân tốt tuy được xem là quân cờ yếu nhất trên bàn cờ vua, nhưng lại hoàn toàn có thể thay đổi cục diện ván cờ sau khi được phong hậu. Chính vì điều đó, Bờm cảm thấy rất hứng thú với quân cờ này. Bờm có 1 bàn cờ kích thước M hàng, N cột và K quân tốt. Hãy giúp Bờm xác định có bao nhiêu cách đặt K quân tốt lên bàn cờ sao cho không quân tốt nào có thể tấn công được nhau, biết rằng quân tốt nằm ở ô (x, y) sẽ tấn công được quân tốt nằm ở ô (x-1, y+1) và (x+1, y+1).
Với N=2, M=2, K=2, ta có 4 cách đặt như sau:
Input:
Dòng đầu chứa T là số bộ test.
T dòng sau mỗi dòng chứa 3 số M, N, K.
Output:
Kết quả mỗi test trên một dòng có dạng:
Case #x: R
Trong đó x là test thứ mấy, bắt đầu tính từ 1. R là phần dư của số cách đặt cho 109.
Giới hạn:
T<=10
Small: M, N<=4, K<=8
Large: M, N<=8, K<=16
Ví dụ:
Input
2
2 2 2
3 2 3
Output
Case #1: 4
Case #2: 6