Description

On an $N \times N$ grid, you start at $(1, 1)$, the top-left corner. Each move, you may only go to the adjacent cell below or to the adjacent cell to the right. How many ways are there to reach $(N, N)$, the bottom-right corner?

However, this problem is too simple, so now there are $M$ cells with obstacles, meaning you cannot step on these $M$ cells.

Input Format

The first line contains two non-negative integers $N, M$, representing the side length of the grid and the number of obstacles.

Then follow $M$ lines, each containing two positive integers $x, y$ that are not greater than $N$. This means there is an obstacle at coordinate $(x, y)$ that cannot be passed, with $1≤x, y≤n$, and at least one of $x, y$ is greater than $1$. Note that obstacle coordinates may be the same.

Output Format

A non-negative integer, which is the result of the answer $\bmod 100003$.

3 1
3 1

5

Hint

For $20\%$ of the testdata, $N≤3$.

For $40\%$ of the testdata, $N≤100$.

For $40\%$ of the testdata, $M=0$.

For $100\%$ of the testdata, $N≤1000,M≤100000$.

Translated by ChatGPT 5