#242EasyMath & Combinatorics· Binomial Coefficients Modulo a Prime

Lattice Delivery Paths

A warehouse robot moves on a rectangular grid of `rows x cols` aisles. It starts at the top-left corner and has to reach the bottom-right corner. In one step it moves either one cell **right** or one cell **down**; it never moves backwards. Count the different routes the robot can take. The number can be astronomically large, so return it modulo `1000000007`.

Input format

`rows` and `cols`: the number of rows and columns of the grid.

Output format

A single integer: the number of routes modulo 1000000007.

Examples

Input: rows = 3, cols = 7

Output: 28

The robot makes 2 down steps and 6 right steps in some order: C(8, 2) = 28 routes.

Input: rows = 2, cols = 2

Output: 2

One down and one right step, in either order: 2 routes.

Input: rows = 1, cols = 5

Output: 1

With a single row the only route is straight to the right.

Constraints

1 <= rows, cols <= 10^5

#combinatorics
#modular-arithmetic
#math
#grid-paths