M. Matrix operations
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Okarun is studying alien art. Alien art is represented by a square matrix that contains blank characters, digits from $$$1$$$ to $$$9$$$, the symbol '$$$+$$$', or the symbol '$$$*$$$'. We call such square matrix an art matrix, and it is defined recursively as follows:

  • A matrix of size $$$1 \times 1$$$ that contains a single digit $$$d$$$ different from $$$0$$$.
  • A matrix of size $$$N \times N$$$ ($$$N \gt 1$$$) that has the same character $$$c$$$ ($$$c \in \{+, *\}$$$) in its four corners, and $$$0$$$ or more non-adjacent art matrices placed inside its inner submatrix.

The inner submatrix is obtained by removing the leftmost and rightmost columns, as well as the top and bottom rows. Two art matrices are considered non-adjacent if there is at least one blank character adjacent to every cell on their borders.

Each art matrix has an associated beauty value $$$b$$$, defined as:

  • If $$$N = 1$$$, then $$$b = d$$$, where $$$d$$$ is the digit contained in the matrix.
  • If $$$N \gt 1$$$ and $$$c = +$$$, then $$$b = \sum\limits_{m \in M} b_m$$$, where $$$M$$$ is the set of art matrices in the inner submatrix. If $$$M$$$ is empty, $$$b = 0$$$.
  • If $$$N \gt 1$$$ and $$$c = *$$$, then $$$b = \prod\limits_{m \in M} b_m$$$, where $$$M$$$ is the set of art matrices in the inner submatrix. If $$$M$$$ is empty, $$$b = 1$$$.

Given an art matrix, tell Okarun the beauty of the matrix.

Input

The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 1000$$$) — the size of the matrix.

The next $$$N$$$ lines each contain a string of $$$N$$$ characters representing the $$$i$$$-th row of the matrix. Blank cells are represented by the '.' character.

Output

Print a single integer $$$b$$$ — the beauty of the Alien art matrix modulo $$$10^9 + 7$$$.

Examples
Input
6
+....+
.3.4..
..1...
....2.
.1.1..
+....+
Output
12
Input
11
+.........+
.*...*.....
..3.3..+.+.
...2....5..
..3.3..+.+.
.*...*.....
...........
...+.+.*.*.
....1...4..
...+.+.*.*.
+.........+
Output
172
Input
2
**
**
Output
1
Input
1
2
Output
2