Bảng kỳ diệu

Cho một bảng gồm $n$ hàng và $m$ cột. Bạn cần điền vào mỗi ô một số nguyên (không giới hạn giá trị) sao cho tích các số trên mỗi hàng và tích các số trên mỗi cột đều bằng $k$, trong đó $k$ chỉ nhận giá trị $1$ hoặc $-1$.

Hãy đếm số cách điền hợp lệ. Hai cách được xem là khác nhau nếu tồn tại ít nhất một ô mà số điền vào ở hai cách là khác nhau.

Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng chứa ba số nguyên $n$, $m$ và $k$.

Dữ liệu ra

In ra một số nguyên duy nhất là số cách điền hợp lệ, lấy phần dư theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n,m\le {10}^{18}$
• $k\in \{1,-1\}$

Ví dụ