[ZJOI2009]多米诺骨牌

有一个 $n\times m$ 的矩形表格，其中一些格子是障碍。现在要在表格中放置若干块大小为 $1\times 2$ 或 $2\times 1$ 的多米诺骨牌，并满足以下条件：

• 任意两块多米诺骨牌互不重叠；
• 任何一块多米诺骨牌都不能覆盖障碍格；
• 任意相邻两行之间，都至少有一块多米诺骨牌横跨这两行；
• 任意相邻两列之间，都至少有一块多米诺骨牌横跨这两列。

你不需要用多米诺骨牌铺满所有非障碍格。请计算不同放置方案的数量。

输入格式

第一行包含两个整数 $n,m$，分别表示表格的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个字符，描述矩形表格。其中字符 x 表示障碍格，字符 . 表示非障碍格。

输出格式

输出一行一个整数，表示不同放置方案数对 $19901013$ 取模后的结果。

样例输入

3 3
...
...
...

样例输出

2

数据范围

• $1\le n,m\le 15$。

来源与许可

本题为 ZJOI 2009 试题「多米诺骨牌」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 3
...
...
...

输出

2