A flood-response map is a grid of R rows and C columns. Each cell is either open (marked 0) or sandbagged and impassable (marked 1). A crew member starts at the top-left cell and must reach the bottom-right cell, moving on each step to the cell immediately to the right or immediately below, and may only stand on open cells.
Count how many distinct right/down routes avoid every sandbagged cell. If the top-left or bottom-right cell is itself sandbagged, there are no valid routes.
Input format
Line 1: two integers R and C.
Next R lines: each contains C integers, each 0 (open) or 1 (sandbagged).
Output format
A single integer: the number of right/down routes from the top-left cell to the bottom-right cell that pass only through open cells.
Constraints
- 1 <= R <= 30
- 1 <= C <= 30
- Each cell is 0 or 1.
- The answer is guaranteed to fit in a signed 64-bit integer.