跳舞的线

Cat 喜欢跳舞的线的音乐，于是就有了这一道题。

给你一个 h×w 的方格棋盘，棋盘上有一颗棋子最开始在左上角 (1,1)，棋子只能往右走或者往下走，棋子最后要走到右下角 (w,h)

在棋子走的过程中，如果当前走的方向与上一次走的方向不同，则称棋子拐了一下弯。

例如下图，棋子在行进过程中拐了三次，也就是有三个拐点。

现在 Cat 想要知道拐点为 k 的时候有多少种走法。

第一行有三个整数 h,w,k（h 行，w 列，k 个拐点）

输出在拐点个数为 k 时有多少种走法。

3 3 2

2

对于 80% 的数据 2≤h,w≤7,1≤k≤h+w−3
对于 100% 的数据 2≤h,w≤15,1≤k≤h+w−3

这道题其实放了很多水，暴力可得80分。