题目描述

有一个$N*N$的方格，起点是$（1,1）$终点是$（N, N）$每次行走只能往右走或者往下走, 但是有一些格子是坏的不能走。

请你统计一下从起点到终点的所有路径，最后答案 $mod \space 100003$。

输入格式

第一行一个数$N, M$，表示$N*N$方格（$1<=N, M<=1000$）,$M$坏格子。
接下来$M$行每行两个数$x_i, y_i(1<x_i<n,1<y_i<n)$,表达第$x_i$行 $y_i$列格子是坏的

输出格式

一行数，路径的个数。

输入样例#1

5 2
1 2
3 1

输出样例#1

20

输入样例#2

5 1
1 2

输出样例#2

35