Cho trước bảng kẻ lưới ô vuông kích thước ~N \times M~ (trong đó ~N~ là số dòng, ~M~ là số cột của bảng) và một số nguyên ~K~. Ban đầu mỗi ô vuông của bảng đều không chứa số nguyên nào. Hãy đếm số cách điền các số nguyên vào tất cả các ô vuông của bảng sao cho tích các số trên cùng hàng và cùng cột bất kì đúng bằng ~K~, với ~K \in \{-1; 1\}~.

Yêu cầu: Hãy tính số cách điền các số nguyên thỏa mãn điều kiện trên và đưa ra kết quả là số dư khi chia cho ~10^9 + 7~.

Input

• Gồm 1 dòng duy nhất chứa 3 số nguyên ~N, M, K~ (~K \in \{-1; 1\}~).

Output

• Gồm 1 số nguyên duy nhất là số dư kết quả bài toán khi chia cho ~10^9 + 7~.

Sample Input 1

1 1 -1

Sample Output 1

1

Sample Input 2

1 3 1

Sample Output 2

1

Sample Input 3

3 3 -1

Sample Output 3

16