题目描述

有 n*m 的矩阵，我们想在这个矩阵一共种 k 棵树，要求每棵树的上下左右没有别的树（即没有树与它相邻），请你输出总方案数。

输入格式

一行三个整数 $n,m,k$

输出格式

一个整数，代表总方案数

样例 #1

样例输入 #1

2 2 1

样例输出 #1

4

样例 #2

样例输入 #2

2 2 2

样例输出 #2

2

提示

对于 $20 \%$ 的数据，满足 $n \times m \leq 6 , k \leq 4$

对于 $100 \%$ 的数据，满足 $n\times m \leq 16 , k \leq 5$