A cleaning rover crosses a tiled plaza with rows rows and cols columns. It starts on the top-left tile and must stop on the bottom-right tile. In one move it goes one tile right, one tile down, or one tile diagonally down-right. Return the number of different trails modulo 10**9 + 7.
Examples
Input: rows = 2, cols = 2
Output: 3
Explanation: right-then-down, down-then-right, or one diagonal move.
Input: rows = 3, cols = 3
Output: 13
Input: rows = 1, cols = 5
Output: 1
Constraints
1 <= rows, cols <= 300- Target complexity: O(rows * cols). The number of trails grows exponentially, so listing them is hopeless.
Goals
- Count routes into a cell from three predecessor cells
- Keep a large count small with a modulus