TABLE — Bảng điểm
Đề bài
Mô tả
Cho một bảng gồm dòng và cột. Bạn được phép tô điểm vào một số ô của bảng, mỗi ô tô không quá một điểm (điểm được tô đúng vào tâm ô).
Bạn muốn việc tô thoả mãn điều kiện sau: mọi bảng con vuông kích thước (gồm dòng và cột liên tiếp) đều chứa đúng điểm.
Hãy đếm số cách tô bảng thoả mãn điều kiện trên. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho .
Hai cách tô được coi là khác nhau nếu tồn tại một ô mà ở cách này có điểm còn ở cách kia thì không.
Dữ liệu vào
Một dòng duy nhất chứa ba số nguyên , , .
Dữ liệu ra
In ra một số nguyên duy nhất — số cách tô bảng thoả mãn, lấy phần dư khi chia cho .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 6 1 | 45 | Bảng có hai bảng con (cột và cột ), chúng giao nhau ở vùng cột . Nếu điểm nằm trong vùng giao thì cả hai bảng con đều nhận được điểm đó: có ô như vậy. Nếu điểm nằm ở cột thì phải có một điểm tương ứng ở cột để bảng con thứ hai cũng đủ điểm: có khả năng. Tổng cộng . |
| 1 1000000000000000000 0 | 1 | Khi , mỗi bảng con là một ô và phải chứa điểm, nên toàn bộ bảng không được tô điểm nào. Đúng một cách. |
| 5 37 25 | 1 | Với , mỗi bảng con phải được tô kín toàn bộ, buộc mọi cột đều phải tô đủ điểm. Chỉ có duy nhất một cách. |
Bình luận