Orchard Drone Routes

A drone surveys an orchard laid out as a grid orchard of 0s and 1s. It starts in the top-left cell, must finish in the bottom-right cell, and in each step moves either one cell right or one cell down. A 1 marks a tree the drone cannot fly over. Return the number of distinct routes modulo 10**9 + 7. If the start or the finish is a tree, there are no routes.

Examples

Input:  orchard = [[0,0,0,0],
                   [0,1,0,0],
                   [0,0,0,1],
                   [0,0,0,0]]
Output: 4

Input:  orchard = [[0,1],
                   [1,0]]
Output: 0
Explanation: both cells next to the start are trees.

Constraints

• 1 <= rows, cols <= 100
• orchard[i][j] is 0 or 1
• Target complexity: O(rows * cols). Enumerating routes one by one is impossible for a 100x100 grid.

Goals

• Fill a grid table where each cell depends on the cell above and the cell to the left
• Treat blocked cells as contributing zero routes
• Reduce a huge count with a modulus at every addition