2170. 画圈圈
#2170. 画圈圈
题目描述
有N行M列的点组成一个点阵。你通过用水平和竖直的线段连接一些相邻的点画若干闭合的回路，将所有的点连接起来，组成一个图形。连的线被视为是内部和外部的界限。其中，有一些点（用和#表示）不用被连接，且用表示的点在必须在图形内部，用#表示的点必须在图形外部。例如：（用＋表示点，－和｜表示线，ｘ表示图形内部）＋－＋－＋－＋－＋－＋ ｜ｘｘｘｘｘｘｘｘｘ｜ ＋ｘ＋－＋－＋ｘ﹡ｘ＋ ｜ｘ｜ ｜ｘｘｘ｜＋－＋ ＃ ＋ｘ＋－＋ ｜ｘ｜＋－＋－＋ ＋ｘ＋－＋ ｜ｘｘｘ｜ ｜ｘｘｘ｜＋－＋－＋ ＋－＋－＋以及＋－＋－＋－＋－＋｜ｘｘｘｘｘｘｘ｜＋ｘ＋－＋－＋ｘ＋｜ｘ｜ ｜ｘ｜＋ｘ＋ ＃ ＋ｘ＋ 注意：这个点是在外部！｜ｘ｜ ｜ｘ｜＋ｘ＋－＋－＋ｘ＋｜ｘｘｘｘｘｘｘ｜＋－＋－＋－＋－＋你要写一个程序来计算一共有多少种连线的方法。我们只关心它模一个大质数123456791的余数。
输入格式
输入的第一行包含两个正整数，分别表示行数N和列数M。接下来N行，每行M个字符表示点的情况（用.*#来表示三种点）。 50%的数据满足：总的方法数小于220000 100%的数据满足： M≤12，N≤20
输出格式
输出一个整数，表示总方法数模123456791的余数。
样例
样例输入
5 6
......
....*.
..#...
......
......
样例输出
117