Turtles

题号：NC233874
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一张 $n$ 行 $m$ 列的网格图，图中的有些格子上面有障碍物，但保证 $(1,1)$ 和 $(n,m)$ 上面都没有障碍物。在 $(1,1)$ 处有两只乌龟，都想要去 $(n,m)$ 。乌龟每次都可以向下或者向右走一格，前提是格子上没有任何障碍物。要求两只乌龟在前往 $(n,m)$ 的路途中不可以相遇，即除了起点和终点，他们的路径没有其他公共点。求出从起点到终点的不同路径对数。答案对 $10^9+7$ 取模。

注： $(route_a,route_b)$ 和 $(route_b,route_a)$ 被视为同一对路径。

输入描述:

第一行包含了,。
后面行，每行有个字符，第行第个字符表示的状态（'.'是空格，'#'是障碍）。

输出描述:

一行，对取模后的从起点到终点的不同路径对数。

示例1

输入

复制

4 5
.....
.###.
.###.
.....

输出

复制

示例2

输入

复制

2 3
...
...

输出

复制

备注:

原题链接：https://codeforces.com/contest/348/problem/D