Migrated from Lutece 1805 矩阵

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小明发现了一种特殊的$N\times M$的矩阵，矩阵里的元素都是$1$或$-1$。假设$A_i$为第 $i$ 行 $(1\leq i\leq N)$ 所有元素的乘积，$B_j$为第 $j$ 列 $(1\leq j\leq M)$ 所有元素的乘积。喜欢搞事情的小明突发奇想，想知道有多少个不相同的，大小为$N\times M$的矩阵使得所有$A_i ,B_j$都是$K$的($K=1$ 或者 $-1$)。
当且仅当两个矩阵存在一个元素不相同时两个矩阵不相同。

Input

输入只有一行，三个数字$N,M,K$。($1\leq N\leq 6, 1\leq M\leq 7,K=1$或者$-1$)

Output

输出一个数字，即满足条件的不同矩阵的数量

Samples

2 2 1

2

Note

这两个不同的矩阵分别是
1 1
1 1
和
-1 -1
-1 -1

Resources

第九届ACM趣味程序设计竞赛第二场（正式赛）