Cho trước bảng kẻ lưới ô vuông kích thước N * 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. 

INPUT: KTABLE.inp

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

OUTPUT: KTABLE.out

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

VÍ DỤ:

RÀNG BUỘC:

• 60% số test ứng với 60% số điểm có: N * M ≤ 20.
• 40% số test ứng với 40% số điểm có: N, M ≤ 10¹⁸