Trên một bảng ô vuông kích thước M ∗N, hãy đếm số cách xếp K quân xe sao cho cả hai điều kiện sau được thỏa mãn:

• Không có hai quân xe nào đứng ở cùng vị trí.

• Không có quân xe nào bị nhiều hơn một quân xe khác tấn công nó.

Hai quân xe được gọi là tấn công được nhau nếu chúng ở cùng hàng hoặc cùng cột.
Dữ liệu • 

Dòng đầu tiên gồm số nguyên dương T (1 ≤ T ≤ 150) là số test.

• T dòng sau, mỗi dòng gồm ba số nguyên dương M,N,K (1 ≤ M,N ≤ 50, 1 ≤ K ≤ 100).
Kết quả

•Gồm T dòng, mỗi dòng đưa ra số cách xếp xe thỏa mãn, sau khi lấy phần dư trong phép chia cho 1000001.