Linh là một cô bé rất thích tô màu. Một hôm, người anh trai của Linh là Long, đã mua tặng chocô một bộ màu nước rất đẹp, nhưng Linh chỉ có thể được dùng bộ màu sau khi giải được câu đốcủa Long. Bạn hãy giúp Linh giải câu đố sau nhé:

Cho một bảng ô vuông có kích thước ~m~ x ~n~ (~m~ hàng, ~n~ cột). Mỗi ô vuông sẽ được tô bởi mộtmà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~ ô vuông đượ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 một dòng chứa 3 số nguyên ~m, n, k~ lần lượt là số hàng, số cột của bảng và số ô vuông phải được tô màu đen

Giới hạn:

• ~(1 ≤ m, n ≤ 10^9)~,
• ~(0 ≤ k ≤ 10^{18})~.

Output

• In ra một số nguyên duy nhất là số cách tô màu các ô trong bảng thỏa mãn điều kiện.

Sample

Input #1

1 5 3

Output #1

1

Input #2

2 2 2

Output #2

2

Problem source: Kc97ble - Free Contest