luogu#P1176. 路径计数2

路径计数2

题目描述

一个 N×NN \times N 的网格,你一开始在 (1,1)(1,1),即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子,问到达 (N,N)(N,N),即右下角有多少种方法。

但是这个问题太简单了,所以现在有 MM 个格子上有障碍,即不能走到这 MM 个格子上。

输入格式

输入文件第 11 行包含两个非负整数 N,MN,M,表示了网格的边长与障碍数。

接下来 MM 行,每行两个不大于 NN 的正整数 x,yx, y。表示坐标 (x,y)(x, y) 上有障碍不能通过,且有 1x,yn1≤x, y≤n,且 x,yx, y 至少有一个大于 11,并请注意障碍坐标有可能相同。

输出格式

一个非负整数,为答案 mod100003\bmod 100003 后的结果。

3 1
3 1
5

提示

对于 20%20\% 的数据,有N3N≤3

对于 40%40\% 的数据,有N100N≤100

对于 40%40\% 的数据,有M=0M=0

对于 100%100\% 的数据,有N1000,M100000N≤1000,M≤100000