Count Paths in a Grid

You are given a grid with (n) rows and (m) columns. Each cell of the grid is either open ('.') or blocked ('#'). Your task is to determine the number of distinct paths from the top-left cell (cell ((1,1))) to the bottom-right cell (cell ((n,m))). You can only move either down or right at any step. The answer must be computed modulo (10^9+7).

Constraints: (1 \leq n, m \leq 1000).

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (m) separated by a space. Then follow (n) lines, each containing a string of length (m). Each character is either a '.' (representing an open cell) or '#' (representing a blocked cell).

outputFormat

Output a single integer to standard output (stdout) which is the number of distinct paths from the top-left cell to the bottom-right cell modulo (10^9+7).## sample

3 4
...#
.#..
....

3