Unique Paths in a Grid

You are given a grid with N rows and M columns that represents souvenir booths. Your task is to determine the total number of unique paths from the top-left booth to the bottom-right booth. You can only move either down or right at any point in time.

The answer should be computed modulo 1000003. Mathematically, the number of unique paths in an $N \times M$ grid with only right and down moves is given by: $$\binom{N+M-2}{N-1} \pmod{1000003}$$

Note: Although the grid contains characters, they do not affect the number of paths.

inputFormat

The first line contains two integers N and M, representing the number of rows and columns respectively.

The following N lines each contain M space-separated characters representing the grid booths.

Input is read from standard input (stdin).

outputFormat

Output a single integer, the total number of unique paths from the top-left to the bottom-right booth modulo 1000003.

Output the answer to standard output (stdout).

3 3
a b c
d e f
g h i

6