Turtles

## 题目描述 一张$n$行$m$列的网格图，图中的有些格子上面有障碍物，但保证$(1,1)$和$(n,m)$上面都没有障碍物。在$(1,1)$处有两只乌龟，都想要去$(n,m)$。乌龟每次都可以向下或者向右走一格，前提是格子上没有任何障碍物。要求两只乌龟在前往$(n,m)$的路途中不可以相遇，即除了起点和终点，他们的路径没有其他公共点。求出从起点到终点的不同路径对数。答案对$10^9+7$取模。 注：$(route_a,route_b)$和$(route_b,route_a)$被视为同一对路径。 ## 输入格式 第一行包含了$n,m$,$(2≤n,m≤3000)$，后面$n$行，每行有$m$个字符，第$i$行第$j$个字符表示$(i,j)$的状态（$'.'$为空格,$'\#'$为障碍物。） ## 输出格式 一行，对$10^9+7$取模后的从起点到终点的不同路径对数。

You've got a table of size $ n×m $ . We'll consider the table rows numbered from top to bottom 1 through $ n $ , and the columns numbered from left to right 1 through $ m $ . Then we'll denote the cell in row $ x $ and column $ y $ as $ (x,y) $ . Initially cell $ (1,1) $ contains two similar turtles. Both turtles want to get to cell $ (n,m) $ . Some cells of the table have obstacles but it is guaranteed that there aren't any obstacles in the upper left and lower right corner. A turtle (one or the other) can go from cell $ (x,y) $ to one of two cells $ (x+1,y) $ and $ (x,y+1) $ , as long as the required cell doesn't contain an obstacle. The turtles have had an argument so they don't want to have any chance of meeting each other along the way. Help them find the number of ways in which they can go from cell $ (1,1) $ to cell $ (n,m) $ . More formally, find the number of pairs of non-intersecting ways from cell $ (1,1) $ to cell $ (n,m) $ modulo $ 1000000007 $ $ (10^{9}+7) $ . Two ways are called non-intersecting if they have exactly two common points — the starting point and the final point.

The first line contains two integers $ n,m $ $ (2<=n,m<=3000) $ . Each of the following $ n $ lines contains $ m $ characters describing the table. The empty cells are marked by characters ".", the cells with obstacles are marked by "\#". It is guaranteed that the upper left and the lower right cells are empty.

In a single line print a single integer — the number of pairs of non-intersecting paths from cell $ (1,1) $ to cell $ (n,m) $ modulo $ 1000000007 $ $ (10^{9}+7) $ .

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

1

2 3
...
...

1