Minefield will come back in classical with harder test cases where O( n^2 ) won't pass!

Leo need to cross minefields, as fast as possible. You are given a map, a square, Leo start at upper left corner and need to join the opposite corner. The only allowed moves are down or right on the map. Sometimes it's possible, sometimes not! You have to count the number of ways Leo can take.

Input

The input begins with the size N of the square in a single line. The next N lines are the description of the map."#" is a mine, "." is a safe place. See the example for details.

Output

Print the number of ways, give your answer modulo 1000000007.

Example 1

Input:
4
....
.#..
##..
.#..

Output:
4

Example 2

Input:
4
...#
.##.
#...
....

Output:
0

At the start of reading third line, one can quickly answer 0.

Constraints:

1 <= N <= 1000

Informations:

Start and stop corner are safe. The density of mines is near 1/4, and in some test cases it is quickly clear that there's no way for Leo.