单点时限: 2.0 sec
内存限制: 512 MB
蟹老板打算扩大梦幻农场的规模,所以他将购置一块新的土地。
在一大片空地中,蟹老板看中了中间的一小片风水宝地。这片风水宝地被划分为 $n$ 行 $m$ 列的方格,每块方格都是单独可购买的地块。由于蟹老板手头并不宽裕,所以他会恰好购买 $k$ 块土地。
蟹老板心想,如果他买下的这 $k$ 块地,刚好可以围出一片未购买的土地,那么其他开发商就自然不乐意大费周折地穿过蟹老板的地盘前去开发,那么久而久之,这块地就会跌价,那么以后等价格合适了再来收购也不迟。所以,蟹老板给买地的任务的任务提出了一些要求:
你想知道一共有多少种满足要求的购买土地的方式,两种方式不同当且仅当有一块土地在一种方案中购买了而在另一种方案中没有。
一行,输入三个整数 $n,m,k$($1\le n,m\le 100,\ 1 \le k \le 12$),分别表示风水宝地的行数、列数和蟹老板打算购买的地块数。
一个整数,表示一共有多少种满足要求的购买土地的方式。
3 3 7
4
5 4 9
546
因为这片 $n$ 行 $m$ 列风水宝地之外也是土地,所以不能只围一个边角。