A courier starts in the top-left cell of a rectangular grid and must reach the bottom-right cell. On every step the courier may move exactly one cell right or one cell down — never left, up, or diagonally.

Each cell is either open (0) or blocked (1). The courier may never stand on a blocked cell. Count how many distinct sequences of moves take the courier from the top-left cell to the bottom-right cell.

Because every step increases either the row or the column by exactly one, two paths are considered distinct if and only if they differ in at least one visited cell.

Input format

Line 1: two integers rows and cols. The next rows lines: each contains cols integers (each 0 or 1), the grid in row-major order.

Output format

A single integer: the number of distinct right/down paths from the top-left cell to the bottom-right cell that avoid every blocked cell. Print 0 if no such path exists (including when the start or end cell is blocked).

Constraints

• 1 ≤ rows ≤ 100
• 1 ≤ cols ≤ 100
• Each grid value is 0 (open) or 1 (blocked).
• The answer fits in a 64-bit-safe integer for the given limits, but Python integers are unbounded so no overflow handling is required.

3 3
0 0 0
0 0 0
0 0 0

6

4 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 1 0

6