[ZJOI2009]多米诺骨牌
题号：NC20485
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

第一行两个整数n,m。
接下来n 行，每行m个字符，表示这个矩形表格。 其中字符“x” 表示这个位置有障碍，字符“.” 表示没有障碍。

输出描述:

一行一个整数，表示不同的放置方法数mod 19901013 的值。
示例1

输入

复制 
3 3
...
...
...

输出

复制 
2

备注:

对于  的数据，满足 ；
对于  的数据，满足 。
对于  的数据，满足 。