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.

Input

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

Output

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

Sample

Input #1

1 5 3

Output #1

1

Input #2

2 2 2

Output #2

2

Problem source: Chuyên Sơn La Online Judge