Description

一个N×N的街区，左上角为[1,1],右下角为[N,N]，（N<100）。现要求出从左上角到右下角的路径总数，每次只能向下或向右走。
路径中有M个街区有障碍（M<10），不能通过，但不会形成到不了终点的情况。
每条路上的汇总路径数都要对10000取余，以免数据溢出。

Input

第一行：两个整数N和M；分别表示街区维度和障碍数；
第二行开始M行：障碍所在的街区。

Output

输出满足题意的路径数。

Sample Input

3 1
3 1

Sample Output

5

HINT

Source

NBU OJ