A building has floors 1 to top. Once a minute the caretaker wrote the lift's floor into a logbook, so log[i] is the floor at minute i. Rain smudged some entries, which now read 0. The lift is slow: between two consecutive minutes it moves at most step floors (it may stay put).
Return how many complete logbooks are possible: ways to replace every 0 with a floor in 1..top so that every pair of consecutive entries differs by at most step. Entries that are not smudged must stay as they are. Answer modulo 10**9 + 7; return 0 if no logbook fits.
Examples
Input: log = [2, 0, 3], top = 3, step = 1
Output: 2
Explanation: the middle entry is 2 or 3.
Input: log = [0, 0], top = 3, step = 1
Output: 7
Explanation: every pair of floors except (1, 3) and (3, 1).
Input: log = [1, 0, 3], top = 5, step = 0
Output: 0
Constraints
1 <= len(log) <= 2000,1 <= top <= 300,len(log) * top <= 3 * 10**50 <= step <= top- every entry is
0or a floor in1..top - Target complexity: O(len(log) * top). Summing over all reachable previous floors for every floor is too slow.
Goals
- Use the current value (floor) as the dp state and roll the table over time
- Replace a window sum over neighbouring states with a prefix-sum difference
- Handle fixed entries by zeroing every other state