| 问题描述 |
|---|
有一个$$n \times n$$的网格，你一开始在$$(1，1)$$即左上角。
在本题中，有$$m$$个位置被放置了障碍，有障碍的方格无法通过。 你每次只能移动到下方相邻的格子或者右方相邻的格子，问到达$$(n，n)$$即右下角有多少种方法？
|
| 输入描述 |
第一行两个正整数$$n,m$$含义如描述。（$$1 \leq n,m \leq 1000$$） 接下来$$m$$行，每行两个正整数$$x,y$$描述一个障碍的位置。（$$1 \leq x,y \leq n$$） |
| 输出描述 |
在一行中输出从左上角走到右下角的方法数。由于答案可能很大，你只需要输出它对$$100003$$取模之后的结果。 |
| 样例输入复制样例 |
3 1 3 1 |
| 样例输出 |
5 |
| 提示说明 |
有可能存在一些障碍处于同一个格子上。 |
| 相关 |