题目描述

有 $n$ 行 $m$ 列的点组成一个点阵。你通过用水平和竖直的线段连接一些相邻的点画若干闭合的回路，将所有的点连接起来，组成一个图形。

连的线被视为是内部和外部的界限。其中，有一些点（用 * 和 # 表示）不用被连接，且用 * 表示的点在必须在图形内部，用 # 表示的点必须在图形外部。例如：（用 + 表示点，－ 和 ｜表示线，ｘ 表示图形内部）

＋－＋－＋－＋－＋－＋
｜ｘｘｘｘｘｘｘｘｘ｜
＋ｘ＋－＋－＋ｘ﹡ｘ＋
｜ｘ｜　　　｜ｘｘｘ｜
＋－＋　＃　＋ｘ＋－＋
　　　　　　｜ｘ｜
＋－＋－＋　＋ｘ＋－＋
｜ｘｘｘ｜　｜ｘｘｘ｜
＋－＋－＋　＋－＋－＋

以及

＋－＋－＋－＋－＋
｜ｘｘｘｘｘｘｘ｜
＋ｘ＋－＋－＋ｘ＋
｜ｘ｜　　　｜ｘ｜
＋ｘ＋　＃　＋ｘ＋
｜ｘ｜　　　｜ｘ｜
＋ｘ＋－＋－＋ｘ＋
｜ｘｘｘｘｘｘｘ｜
＋－＋－＋－＋－＋
注意：这个点是在外部！

你要写一个程序来计算一共有多少种连线的方法。我们只关心它模一个大质数 $123456791$ 的余数。

输入格式

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

接下来 $n$ 行，每行 $m$ 个字符表示点的情况（用 .*# 来表示三种点）。

输出格式

输出一个整数，表示总方法数模 $123456791$ 的余数。

样例输入

5 6
......
....*.
..#...
......
......

样例输出

117

数据范围与约定

$50\%$ 的数据满足：总的方法数小于 $2.2\times 10^5$。

$100\%$ 的数据满足：$m\leq 12$，$n\leq 20$。

题目来源

版权所有者：范浩强