A canal network is a grid of R rows and C columns; each cell charges a non-negative toll collected when a barge enters it (the top-left starting cell is always entered). A barge starts at the top-left cell and must reach the bottom-right cell, moving on each step to the cell immediately right or immediately below.
Among all such routes, some achieve the smallest possible total toll. Determine how many distinct routes achieve that minimum total.
Input format
Line 1: two integers R and C.
Next R lines: each contains C non-negative integers, the tolls of that row.
Output format
A single integer: the number of distinct right/down routes whose total toll equals the minimum achievable total toll.
Constraints
- 1 <= R <= 30
- 1 <= C <= 30
- 0 <= each toll <= 1000
- The answer is guaranteed to fit in a signed 64-bit integer.