A robotics team at a high-throughput e-commerce fulfillment center routes pick-and-pack robots across a warehouse grid. Some floor tiles are temporarily blocked (spills, pallets, safety zones). Each robot can activate exactly one “override” during its trip, allowing it to traverse one blocked tile (and only one). Because the system serves millions of picks/day, you need an efficient way to count how many valid routes exist.
You are given an m x n grid grid where:
grid[i][j] == 0 means the tile is freegrid[i][j] == 1 means the tile is blockedA robot starts at the top-left cell (0, 0) and must reach the bottom-right cell (m-1, n-1). It may move only:
(i, j) -> (i, j+1)(i, j) -> (i+1, j)A route is counted if and only if the robot steps on exactly one blocked cell total along the entire route (the override is used exactly once). The start and end cells are included as stepped-on cells.
Return the number of such routes modulo 1_000_000_007.
Example 1
grid = [[0,0,0],[0,1,0],[0,0,0]]4(1,1) (the only blocked cell). Those 4 routes use the override on (1,1) and are valid. The other 2 routes avoid all blocked cells and are invalid because the override must be used exactly once.Example 2
grid = [[0,1],[1,0]]2(0,1)) and Down→Right (hits (1,0)). Each hits exactly one blocked cell, so both are counted.0.[[0]], there is a route of length 0 that steps on 0 blocked cells, so the answer is 0.[[1]], the route steps on exactly one blocked cell (the start), so the answer is 1.