CF348D.Turtles

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 (109 + 7). Two ways are called non-intersecting if they have exactly two common points — the starting point and the final point.

你有一个大小为 $n \times m$ 的表格。我们将表格的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。记第 $x$ 行第 $y$ 列的格子为 $(x, y)$。

初始时，格子 $(1, 1)$ 中有两只相同的乌龟。两只乌龟都希望到达格子 $(n, m)$。表格中某些格子存在障碍物，但保证左上角 $(1, 1)$ 和右下角 $(n, m)$ 均无障碍物。一只乌龟（任一只）可以从格子 $(x, y)$ 移动到以下两个格子之一：$(x+1, y)$ 或 $(x, y+1)$，前提是目标格子不包含障碍物。由于这两只乌龟发生了争执，它们不希望在路径中有任何相遇的可能。请你帮它们计算：从格子 $(1, 1)$ 同时出发、各自抵达格子 $(n, m)$，且路径互不相交的方案总数。

更严格地说，求从 $(1, 1)$ 到 $(n, m)$ 的两条互不相交路径的有序对数量，结果对 $1000000007$（即 $10^9 + 7$）取模。若两条路径仅有两个公共点——起点和终点，则称它们互不相交。

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.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 3000$）。接下来的 $n$ 行，每行包含 $m$ 个字符，用于描述表格。空单元格用字符 . 表示，障碍物单元格用字符 # 表示。

保证左上角和右下角的单元格均为空。

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 (109 + 7).

在一行中输出一个整数——从单元格 $(1,1)$ 到单元格 $(n,m)$ 的不相交路径对的数量，对 $1000000007$（即 $10^9 + 7$）取模。