给定一个 N×M 的网格图，每个格子初始为白色，现在需要将 K 个格子染成黑色，使得每行每列的黑格子数均为奇数，求方案数。
输入格式
一行三个整数 N,M,K。
输出格式
输出一行一个整数，表示方案数 mod 的结果。
样例一
input
3 3 5
output
9
样例二
input
500 1000 1000
output
928165755
数据范围
| 测试点编号 | N,M | K |
|---|---|---|
| 1,2 | N \times M \le 20 | |
| 3,4 | N \times M \le 100 | |
| 5,6 | N \times M \le 5000 | K \le 100 |
| 7,8 | N \times M \le 5000 | |
| 9,10,11 | N \times M \le 10^5 | |
| 12,13 | N \times M \le 5 \times 10^5 | K \in \{N,M\} |
| 14,15 | N \times M \le 5 \times 10^5 | K \le 1000 |
| 16,17,18,19,20 | N \times M \le 5 \times 10^5 |
对于所有数据，保证 N,M 为正整数， 0 \le K \le N \times M ，对于所有编号为偶数的点，有 N=M 。