2920. 蒙德里安的梦想
时间限制：1000 MS 内存限制：128 MB
题目描述
# 蒙德里安的梦想 ## 题目描述 给定一个 $N\times M$ 的棋盘，求用若干个 $1\times 2$ 的长方形完整覆盖棋盘的方案数。 每个长方形可以横放或竖放，恰好覆盖两个相邻的格子。所有格子都必须被覆盖，且长方形之间不能重叠。 例如，当 $N=2$、$M=4$ 时，共有 $5$ 种方案；当 $N=2$、$M=3$ 时，共有 $3$ 种方案。 如下图所示：  ## 输入格式 从文件 `mondrian.in` 中读入数据。 输入包含多组测试用例。 每组测试用例占一行，包含两个整数 $N$ 和 $M$，表示棋盘的行数和列数。 当读入的一行为 `0 0` 时，表示输入结束，该行不需要处理。 ## 输出格式 将结果输出到文件 `mondrian.out` 中。 对于每组测试用例，输出一个整数，表示完整覆盖棋盘的方案数。每个结果占一行。 ## 数据范围 对于每组测试用例，$1\le N,M\le 11$。 时间限制：$1000$ 毫秒。 内存限制：$128$ MB。 ## 样例输入 ``` 1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0 ``` ## 样例输出 ``` 1 0 1 2 3 5 144 51205 ```