你有一个大小为 n × m 的表。我们将考虑从上到下编号为 1 到 n 的表行,以及从左到右编号为 1 到 m 的列。然后我们将第 x 行和第 y 列中的单元格表示为 (x, y)。
最初,单元格 (1, 1) 包含两只相似的海龟。两只乌龟都想到达单元格 (n, m)。表格的某些单元格有障碍物,但保证左上角和右下角没有任何障碍物。一只海龟(其中之一)可以从单元格 (x, y) 移动到两个单元格 (x + 1, y) 和 (x, y + 1) 之一,只要所需的单元格不包含障碍物即可。海龟们发生了争执,所以他们不想在路上有任何机会见面。帮助他们找出从单元格 (1, 1) 到单元格 (n, m) 的方式有多少种。
更正式地说,求从单元格 (1, 1) 到单元格 (n, m) 模 1000000007 (109 + 7) 的非相交路径对的数量。如果两条路恰好有两个公共点——起点和终点,则称为不相交。
输入
第一行包含两个整数 n, m (2 ≤ n, m ≤ 3000)。以下 n 行中的每一行包含描述该表的 m 个字符。空单元格用字符“.”标记,有障碍物的单元格用“#”标记。
保证左上角和右下单元格为空。
输出
在一行中打印一个整数 — 从单元格 (1, 1) 到单元格 (n, m) 的非相交路径对的数量模 1000000007 (109 + 7)。
示例
输入 #1
4 5 ..... .###. .###. .....
输出 #1
1
输入 #2
2 3 ... ...
输出 #2
1