A. BWTILE - Tô màu

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Cho một bảng ô vuông có kích thước m×n ( m hàng, n cột). Mỗi ô vuông sẽ được tô bởi một màu trắng hoặc đen. Hỏi có bao nhiêu cách tô màu các ô trong bảng thỏa mãn điều kiện:

  • Có chính xác k ô được tô màu đen;
  • Không có bất kỳ 2 ô chung cạnh nào được tô cùng một màu.

Dữ liệu: Gồm ba số nguyên m,n,k\ (1≤m,n≤10^9;0≤k≤10^{18}) .

Kết quả: Ghi ra một số nguyên duy nhất là số cách tô màu thỏa mãn.

Ví dụ:

Dữ liệu:

1 5 3

Kết quả:

1

Dữ liệu:

2 2 2

Kết quả:

2