题目内容

小钟拿着积木，要铺到高 $h$、宽 $w$ 的格子盘上。盘里若干格被标成特殊格，小钟手头有无穷多块长度为 $1\times 3$ 以及 $3\times 1$ 的积木。每一次落下一座积木都得同时满足：该积木两端里至少有一端落在特殊格上，落点必须落在盘内且禁止出界，并且此刻要落下的积木不得盖住已经落下的积木所占用的格子。小钟会持续按这些规则往下摆，直到再也摆不进去为止。

小爱在旁边观察小钟铺积木，她想弄清格子盘最后会有几种可能的终态。两个终态被判定为不一样，恰好发生在：盘上找得到某一格，在其中一个终态里该格被积木盖住，在另一个终态里该格空着。请统计格子盘最后会有多少种可能的终态。切记，终态是否算两份，跟落子次序无关，只看各格盖没盖住!

$1\le h,w\le 8$。保证特殊格个数至多 $13$，测例系随机造出。

输入描述

首行给出两个整数 $h(1\le h\le 8)、w(1\le w\le 8)$，依次给出格子盘的高与宽.

随后 $h$ 行，每行读入 $w$ 个字符，若格子盘第 $p$ 行第 $q$ 列这一格属于特殊格，则该行第 $q$ 个字符写成 "*"，不然写成 "."。

输出描述

打印一个整数，即格子盘最后可能出现的终态种数。

样例1

输入

3 4
*...
....
...*

输出

4

说明

本数据下极大铺法对应 $4$ 种不同的覆盖集合，例如：

***.
....
.***

****
...*
...*

*...
*...
****

*..*
*..*
*..*

样例2

输入

2 3
***
***

输出

1

说明

高只有 $2$，竖条放不进去，两行各横放一块即唯一极大铺法，故终态种数是 $1$。