#231. 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
Đưa lên bởi: Chùm CUỐI

Đề 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 vào:

  • Gồm ba số nguyên m,n,k\ (1≤m,n≤10^9;0≤k≤10^{18}) .

Dữ liệu ra:

  • 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 vào:
1 5 3
Dữ liệu ra:
1
Dữ liệu vào:
2 2 2
Dữ liệu ra:
2