Count Up-Right/Right/Down-Right Grid Paths Through Ordered Checkpoints

You are given an `n x m` grid. Rows are numbered `0` to `n - 1` from top to bottom, and columns `0` to `m - 1` from left to right. A path starts at the bottom-left cell `(n - 1, 0)` and ends at the bottom-right cell `(n - 1, m - 1)`. From cell `(r, c)`, one move goes to one of: - `(r - 1, c + 1)` (up-right), - `(r, c + 1)` (right), - `(r + 1, c + 1)` (down-right), and the move must stay inside the grid. You are also given a list of checkpoint cells. Count the paths that visit every checkpoint, in the order in which the checkpoints are listed, and return the count modulo `1_000_000_007`. The interviewer built this up in three steps: first count all paths with no checkpoints; then count the paths that pass through every checkpoint; then require the checkpoints to be visited in a given order and optimize the space complexity. This function is the final step, and an empty checkpoint list gives the first step. Aim for extra memory that does not grow with `m`. ### Function Signature ```python def count_paths(n: int, m: int, checkpoints: list[list[int]]) -> int: ``` ### Rules - `checkpoints[i] = [r_i, c_i]` is a cell of the grid. A path visits a checkpoint when the checkpoint is one of the cells on the path, including the start and end cells. - Every move advances exactly one column, so a path contains exactly one cell of each column. - The path must visit checkpoint `i` before checkpoint `i + 1` for every `i`. Return `0` if no path does. - When `m = 1`, the start and end are the same cell, and the only path makes no moves. ### Constraints - `1 <= n <= 1000` and `1 <= m <= 1000` - `0 <= len(checkpoints) <= 1000` - `0 <= r_i < n` and `0 <= c_i < m`, and the checkpoint cells are distinct. - The exact number of paths can have hundreds of digits, which is why the answer is taken modulo `1_000_000_007`. Each residue fits in a 32-bit signed integer, but a sum of three residues can exceed `2^31 - 1`. ### Examples **Example 1** ```text Input: n = 3, m = 4, checkpoints = [] Output: 4 ``` Writing a path as the row it occupies in each column, the paths are `2, 1, 1, 2`, `2, 1, 2, 2`, `2, 2, 1, 2` and `2, 2, 2, 2`. **Example 2** ```text Input: n = 3, m = 4, checkpoints = [[1, 1], [2, 2]] Output: 1 ``` Only `2, 1, 2, 2` passes through `(1, 1)` and then `(2, 2)`. **Example 3** ```text Input: n = 3, m = 4, checkpoints = [[2, 2], [1, 1]] Output: 0 ``` `(2, 2)` lies in a later column than `(1, 1)`, so no path can visit it first.