U204630 状态压缩-例3

有一个n×m的棋盘(n、m≤80,n×m≤80)要在棋盘上放k(k≤40)个棋子，使得任意两个棋子不相邻；且有些格子不能放，求合法的方案总数。

输入n,m,k

输出方案数

2个棋子在1行：3种 2个棋子在2行：6+6+9种