Counting Distinct Paths with Jump Moves

You are given a grid of size \(N \times M\) consisting of walkable cells denoted by . and non-walkable cells denoted by #. Your task is to determine the number of distinct paths from the top-left corner to the bottom-right corner.

You can only move either down or right at any step. In addition to these moves, you are allowed to perform a jump move: if one of the adjacent moves (either right or down) is blocked by an obstacle while the other is not, you can jump diagonally from the top-left neighbor into the current cell. Formally, if you are at cell \((i, j)\) and both \(i>0\) and \(j>0\), then if either:

• the cell \((i, j-1)\) is blocked (i.e. #) and \((i-1, j)\) is walkable, or
• the cell \((i-1, j)\) is blocked and \((i, j-1)\) is walkable,

you can add the number of ways to reach \((i-1, j-1)\) to the number of ways to reach \((i, j)\) as a jump move.

Since the number of paths can be very large, output the answer modulo \(10^9+7\).

inputFormat

The input is read from standard input and has the following format:

• The first line contains two integers \(N\) and \(M\) representing the number of rows and columns respectively.
• The next \(N\) lines each contain a string of length \(M\) comprised of characters . and # indicating a walkable or non-walkable cell.

It is guaranteed that \(1 \leq N, M \leq 1000\).

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner modulo \(10^9+7\>.

## sample

3 3
..#
.#.
...

2