P2595 [ZJOI2009] 多米诺骨牌

有一个 $n \times m$ 的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些 $1 \times 2$ 或者 $2 \times 1$ 的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨，任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法，注意你并不需要放满所有没有障碍的格子。

无

无

### 样例解释 两种放置方法分别为： ```plain 112 411 4.2 4.2 433 332 ``` 注意这里的数字只用于区分骨牌，不同的排列并不代表不同的方案。 ### 数据范围 - 对于 $40\%$ 的数据，满足 $n,m \leq 8$； - 对于 $90\%$ 的数据，满足 $n,m \leq 14$。 - 对于 $100\%$ 的数据，满足 $1 \leq n,m \leq 15$。