A pollen grain drifts across a greenhouse panel modeled as a grid of R rows and C columns. Each cell is open (0) or blocked by a strut (1). Starting at the top-left cell, the grain drifts to the bottom-right cell; from cell (r, c) it may move to (r, c+1), (r+1, c), or (r+1, c+1), and may only land on open cells.
Count how many distinct routes reach the bottom-right cell landing only on open cells. If the top-left or bottom-right cell is blocked, 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 (blocked).
Output format
A single integer: the number of right/down/diagonal routes from the top-left cell to the bottom-right cell that land only on open cells.
Constraints
- 1 <= R <= 12
- 1 <= C <= 12
- Each cell is 0 or 1.
- The answer is guaranteed to fit in a signed 64-bit integer.