题目描述

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

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

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

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

输入格式

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

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

一个正整数，所求如上。

3 3
.#.
..#
#..

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

$(1,2)\rightarrow(2,2)$
$(1,2)\rightarrow(1,1)$
$(1,2)\rightarrow(1,3)$
$(1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)$
$(2,3)\rightarrow(1,3)$
$(2,3)\rightarrow(3,3)$
$(2,3)\rightarrow(2,2)$
$(2,3)\rightarrow(2,2)\rightarrow(1,2)\rightarrow(1,1)$
$(3,1)\rightarrow(2,1)$
$(3,1)\rightarrow(3,2)$

2 4
....
....

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