#P1292. 棋盘(chess)
棋盘(chess)
题目描述
小Q拿出了一张 行 列的棋盘,棋盘的每个位置可以放一颗黑棋或者一颗白棋。
若两个棋子颜色相同且位置相邻我们就认为这两个棋子连成了一片,这里的位置相邻指的是 相邻,即一个棋子只和上下左右 个棋子相邻。当然两个棋子都和另一个棋子连成一片,我们也认为这两个棋子连成一片。
这天小杜突发奇想,小杜想知道这个棋盘上有多少种放棋子的方法使得棋盘上的棋子片数为 。
这个数目可能非常大,请输出方法对 取模的结果。
输入描述
两个数 和 ,用空格隔开。
输出描述
一个数字表示方案数。
样例
| chess.in | chess.out |
|---|---|
| 3 4 | 12 |
数据范围
对于30%的数据,。
对于50%的数据,。
对于100%的数据,。