---
# System prepended metadata

title: Ways Of Turtle

---

# 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 diﬀerent ways for the turtle to reach the rightmost bottom corner.

## Input format
The ﬁrst 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
```

