P1176 Path Counting 2

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.

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.

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

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