Bài toán quân tốt, giải thuật như thế nào?

[ngoaho]

em gặp bài toán ở đây, http://codepro.edulab.com.vn/Contest...T=13TH&MaBai=B
nội dung của nó như thế này

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

em không biết làm như thế nào, có bác nào biết không chỉ em mấy

[mini_bestboy]

Mình coi sơ qua thì chắc bạn có thể dùng quay lui để giải bài này ! Mặc dầu là không chắc có thể giải hoàn toàn được bài toán !