Unique Paths in a Grid

This problem requires you to calculate the number of unique paths from the top-left corner of a grid to every other cell. You are given a grid of size \(n \times m\). Starting from cell (0, 0), you can only move either to the right or down. The value at each cell (i, j) is the number of unique paths from the starting cell to that cell.

The recurrence relation is given by:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) for \(i, j \geq 1\) with the base cases \(dp[i][0] = 1\) for all \(i\) and \(dp[0][j] = 1\) for all \(j\).

Your task is to read the integers \(n\) and \(m\) from standard input and output the \(n \times m\) matrix where each element is the number of unique paths to that cell. Each row should be printed on a new line with the numbers separated by a single space.

inputFormat

The input consists of two integers (n) and (m) separated by a space. (n) represents the number of rows and (m) represents the number of columns in the grid.

outputFormat

Output the (n \times m) matrix where each cell (i, j) contains the number of unique paths from the top-left corner (0, 0) to (i, j). Each row of the matrix should be printed on a separate line with numbers separated by a single space.## sample

3 3

1 1 1
1 2 3
1 3 6