Bobo bought an $n \times m$ plot of land at ICPCCamp, where some cells are obstacles.

He wants to select two rectangular areas to build two houses. Obviously, the areas used for building houses cannot contain any obstacles. Furthermore, the two areas cannot intersect (though they may be adjacent).

Bobo wants to know the number of all possible distinct schemes modulo $(10^9 + 7)$.

Input

The input contains no more than 10 test cases.

The first line of each test case contains two integers $n, m$ ($1 \leq n, m \leq 10^3$).

The next $n$ lines each contain a string $s_i$ of length $m$. The $j$-th character of $s_i$ is 0 if the cell at the $i$-th row and $j$-th column is empty, and 1 if the cell is an obstacle.

Output

For each test case, output an integer representing the required value.

Examples

Input 1

2 2
00
01

Output 1

5

Input 2

3 4
1000
0001
0100

Output 2

160