A robot starts its journey at the top-left corner of a grid that measures m x n (m rows by n columns).
At each step, the robot has only two possible directions: it can either move to the right or move downward. Its destination is the bottom-right corner of the grid.
Determine the total number of unique paths the robot can take to reach its destination.
Input & Output
Input
m — the number of rows in the grid
n — the number of columns in the grid
Output
the number of unique paths from the top-left corner to the bottom-right corner
Example
Input
m = 2, n = 3
Output
3
Explanation
With 2 rows and 3 columns the robot makes one move down and two moves right, in some order: Right → Right → Down, Right → Down → Right, and Down → Right → Right.
Example
Input
m = 5, n = 3
Output
15
Explanation
The robot makes 4 moves down and 2 moves right, and the answer counts the distinct orderings of those 6 moves. Enumerating them by hand already stops being practical at this size.
Constraints
1 <= m, n <= 100- The answer is guaranteed to fit in a 32-bit signed integer