Unique Paths

A robot starts at the top-left cell of an m × n grid and wants to reach the bottom-right cell. It can only move right or down. How many different paths are there? The number gets huge, so print it modulo 1 000 000 007.

Input: one line m n.

Output: the number of paths modulo 10⁹ + 7.

Constraints: 1 ≤ m, n ≤ 1000.

Think about it: the number of ways to reach a cell = ways to reach the cell above + ways to reach the cell on the left. One row of the table is enough. (There is also a formula with binomial coefficients — but the DP idea is what generalises to grids with obstacles.)