Yeongjae's Stepping Stones

Interview

Time limit0.5sMemory limit512 MB

Summary

Count the paths across an N by M glass bridge where each step moves to one of three adjacent cells in the next row and only tempered glass cells may be stepped on, modulo 1,000,000,007.

Level: Easy3 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

The Puang game participant Yeongjae must get through a glass stepping stone game.

The rules of the glass stepping stone game are simple. The bridge can be crossed in $N$ steps, and each step has $M$ cells. Yeongjae starts from one cell in the starting row ( $N-1$ th row) and, on each following step, may choose one of up to 3 adjacent glass panes ahead to cross. If the cell stepped on is tempered glass, it can be crossed safely, but regular glass cannot be stepped on.

The figure below shows the moves Yeongjae can make at one moment with $N = 3$ , $M = 5$ .

Given the bridge information, find the number of ways Yeongjae can cross the bridge safely.

Input

The first line contains $N$ and $M$ ( $1 \le N, M \le 1{,}000$ ) separated by a space. The next $N$ lines describe the bridge.

A tempered glass cell is given as 1, and a regular glass cell as 0.

Output

Print the number of ways Yeongjae can cross the bridge safely, modulo $1{,}000{,}000{,}007$ .

Examples3

Example 1
Input
```
3 2
0 1
1 0
0 1
```
Expected output
```
1
```

Example 2

Input

Expected output

Example 3
Input
```
4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1
```
Expected output
```
8
```