多米诺骨牌 ### 题目描述 有一个 $n \times m$ 的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些 $1 \times 2$ 或者 $2 \times 1$ 的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨，任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法，注意你并不需要放满所有没有障碍的格子。 ### 输入描述 第一行两个整数 $n,m$。 接下来 $n$ 行，每行 $m$ 个字符，表示这个矩形表格。其中字符 `x` 表示这个位置有障碍，字符 `.` 表示没有障碍。 其中， $1 \leq n,m \leq 15$。 ### 输出描述 输出一行一个整数，表示不同的放置方法数对 $19\,901\,013$ 取模的值。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 3 ... ... ... ``` >输出 ```txt 2 ```