774. Count Paths from Top-Left to Bottom-Right (Modulo 10^9+7)

Given an m x n grid, count how many distinct paths traverse from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1), moving only DOWN or RIGHT at each step. Return the count modulo 10^9 + 7. The original 'print all paths' problem is reformulated as a count to give a deterministic output.

This problem is equivalent to Unique Paths but presented as a counting/enumeration exercise; implement it recursively (with memoization) from the perspective of 'number of paths produced by a recursive path-enumeration function'.

Input: Two positive integers m and n separated by a comma.

Output: Return an integer equal to the number of distinct paths mod (10^9 + 7).

Examples

Input: 2, 2
Output: 2
Explanation: Two paths in a 2x2 grid.

Input: 3, 3
Output: 6
Explanation: C(4,2) = 6 paths.

Input: 1, 5
Output: 1
Explanation: A single row has one path.

Constraints

• 1 <= m, n <= 100

Asked by