4319. 购置土地

单点时限: 2.0 sec

内存限制: 512 MB

蟹老板打算扩大梦幻农场的规模,所以他将购置一块新的土地。

在一大片空地中,蟹老板看中了中间的一小片风水宝地。这片风水宝地被划分为 $n$ 行 $m$ 列的方格,每块方格都是单独可购买的地块。由于蟹老板手头并不宽裕,所以他会恰好购买 $k$ 块土地。

蟹老板心想,如果他买下的这 $k$ 块地,刚好可以围出一片未购买的土地,那么其他开发商就自然不乐意大费周折地穿过蟹老板的地盘前去开发,那么久而久之,这块地就会跌价,那么以后等价格合适了再来收购也不迟。所以,蟹老板给买地的任务的任务提出了一些要求:

  • 首先,为了方便后续开发,购买的土地要是四联通的(即上下左右联通);
  • 其次,蟹老板希望自己购买的土地恰好围住了一片未购买区域,即恰好将整个空地分为了两块,同一块之间的土地都可以通过在未购买土地中上下左右移动到达,而不是同一块的就不能。

你想知道一共有多少种满足要求的购买土地的方式,两种方式不同当且仅当有一块土地在一种方案中购买了而在另一种方案中没有。

输入格式

一行,输入三个整数 $n,m,k$($1\le n,m\le 100,\ 1 \le k \le 12$),分别表示风水宝地的行数、列数和蟹老板打算购买的地块数。

输出格式

一个整数,表示一共有多少种满足要求的购买土地的方式。

样例

Input
3 3 7
Output
4
Input
5 4 9
Output
546

提示

因为这片 $n$ 行 $m$ 列风水宝地之外也是土地,所以不能只围一个边角。

3 人解决,6 人已尝试。

3 份提交通过,共有 24 份提交。

8.7 EMB 奖励。

创建: 3 年,5 月前.

修改: 3 年,5 月前.

最后提交: 3 年,5 月前.

来源: N/A

题目标签