题目描述

小明站在一个 $N \times N$ 的方格迷宫的左上角 $(1, 1)$，他想要走到右下角 $(N, N)$。每一步只能向右或向下移动到相邻格子。

迷宫中有 $M$ 个格子被设置了路障，不能经过。请帮小明计算从起点到终点有多少条不同的路径。

由于答案可能很大，请将结果对 $100003$ 取模后输出。

输入格式

输入文件第 $1$ 行包含两个非负整数 $N$ 和 $M$，分别表示迷宫的边长与路障数量。

接下来 $M$ 行，每行两个正整数 $x, y$，表示坐标 $(x, y)$ 处有路障。其中 $1 \le x, y \le N$，且 $x, y$ 至少有一个大于 $1$。请注意路障坐标可能重复。

输出格式

一个非负整数，表示路径数对 $100003$ 取模后的结果。

样例

3 1
3 1

5

提示

对于 $20\%$ 的数据，有 $N \le 3$；

对于 $40\%$ 的数据，有 $N \le 100$；

对于 $40\%$ 的数据，有 $M = 0$；

对于 $100\%$ 的数据，有 $N \le 10^3$，$M \le 10^5$。