# Ways Of Turtle

There is an $N \times M$ rectangular grid. The turtle is in the leftmost top corner. Each cell of the grid is either open or closed. The turtle can make moves of three types:
* 1 step down,
* 1 step to the right, or
* 1 step in diagonal direction (one down then one right) in a single move.

The turtle cannot step into a closed cell. Calculate the number of different ways for the turtle to reach the rightmost bottom corner.

## Input format
The first line contains two integers $N, M$ ($1 \le N, M \le 1000$). The following $N$ lines contain the description of the grid. Each of the lines contains $M$ integers — $0$ if the cell is open and $1$ if the cell is closed. You may assume that both starting and ending cells are open.

## Output format
Print one integer — the number of ways to reach the rightmost bottom corner of the grid. Since the answer may be too big, print it modulo $10^9 + 9$.

### Sample 1

#### Input

3 5
0 0 1 0 0
1 1 0 1 1
0 0 0 0 0

#### Output

2

### Sample 2

#### Input

5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

#### Output

321