题目描述

小$\tt Z$ 在一次探险中，踏入了一座古老神秘的遗迹。这座遗迹由一个 $n\times m$ 的矩形房间阵列构成，每个房间要么藏着珍贵的宝石（标记为 #），要么布满致命的陷阱（标记为 .）。

探险过程中，小$\tt Z$ 发现了一个特殊规律：只有按照 “宝石 - 陷阱 - 宝石 - 陷阱...” 这样交替的顺序，才能在遗迹中安全穿行。

现在小$\tt Z$ 好奇，在这座遗迹里，从藏有宝石的房间出发，以布满陷阱的房间为终点，一共有多少种不同的安全路线组合？快来帮助小$\tt Z$ 解开这个谜题吧！

注：不管具体的路线方案，只要起点终点相同，就视为同一种路线

输入格式

第一行，$2$ 个正整数 $n,m$ 表示遗迹的长宽。

接下来 $n$ 行 $m$ 列的字符，分别为 # 或 . 。

输出格式

一个正整数，所求如上。

输入输出样例

3 3
.#.
..#
#..

10

样例 $\tt \#1$说明

以上地图中有 $10$ 条安全路线：

1. $(1,2)\rightarrow(2,2)$
2. $(1,2)\rightarrow(1,1)$
3. $(1,2)\rightarrow(1,3)$
4. $(1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)$
5. $(2,3)\rightarrow(1,3)$
6. $(2,3)\rightarrow(3,3)$
7. $(2,3)\rightarrow(2,2)$
8. $(2,3)\rightarrow(2,2)\rightarrow(1,2)\rightarrow(1,1)$
9. $(3,1)\rightarrow(2,1)$
10. $(3,1)\rightarrow(3,2)$

2 4
....
....

0

4 3
###
###
...
###

6

数据范围

• 对于 $10\%$ 的数据：$1\le n,m\le 2$
• 另外 $10\%$ 的数据：$n = 1$
• 对于 $100\%$ 的数据：$1\le n, m\le 400$