Unique Paths in a Grid

In this problem, you are given a grid with m rows and n columns. Your task is to calculate the number of unique paths from the top-left corner to the bottom-right corner. You can only move either down or right at any point in time.

The problem can be solved using dynamic programming. Start by initializing a 2D array with the value 1 at each cell for the first row and first column. Then, the number of ways to reach a cell is the sum of ways to reach the cell above it and the cell to the left of it. In mathematical terms, if we denote by dp[i][j] the number of unique paths to cell (i, j), then the recurrence relation is:

$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$

The final answer will be the value at the bottom-right corner, i.e., dp[m-1][n-1].

inputFormat

The input consists of two integers m and n separated by a space, representing the dimensions of the grid (number of rows and columns respectively).

outputFormat

Output a single integer representing the number of unique paths from the top-left corner to the bottom-right corner of the grid.## sample

3 7

28