UOJ Logo

NOI.AC

1S 512MB
Statistics

题目描述

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

输入格式

一行三个整数 n,m,k

输出格式

一个整数,代表总方案数

样例 #1

样例输入 #1

2 2 1

样例输出 #1

4

样例 #2

样例输入 #2

2 2 2

样例输出 #2

2

提示

对于 20% 的数据,满足 n×m6,k4

对于 100% 的数据,满足 n×m16,k5