MinimumCostPath

Time Limit : 5 sec, Memory Limit : 262144 KB

MinimumCostPath

NxNの方眼がある。


(N=3の場合の図)

隣接するマス目に移動するにはコストが1かかる。ただし、斜めに移動することは出来ない。 また障害物があるマス目がM個あり、そのマスに入ることは許されない。 マス(1, 1)からマス(N, N)に最小のコストで移動する方法は何通りあるか。 答えは大きくなることがありうるので、1000000009(=109+9)でMODを取って出力せよ。

Input

入力は以下の形式で与えられる

N M
X1 Y1
X2 Y2
……
XM YM

Xi, Yiは(Xi, Yi)に障害物があることを表す

Constraints

  • 2 ≤ N ≤ 106

  • 0 ≤ M ≤ 50

  • 1 ≤ Xi , Yi ≤ N

  • i ≠ jならば (Xi, Yi) ≠ (Xj, Yj)

  • (Xi, Yi) ≠ (1, 1)

  • (Xi, Yi) ≠ (N, N)

Output

1行に経路の総数を出力せよ。ただし、マス(1, 1)からマス(N, N)に移動する経路が存在しない場合は0と出力せよ。

Sample Input 1

3 0

Output for the Sample Input 1

6
以下の図に対応する。

Sample Input 2

3 1
2 2

Output for the Sample Input 2

2
以下の図に対応する。

Sample Input 3

5 8
4 3
2 1
4 2
4 4
3 4
2 2
2 4
1 4

Output for the Sample Input 3

1
以下の図に対応する。

Sample Input 4

1000 10
104 87
637 366
393 681
215 604
707 876
943 414
95 327
93 415
663 596
661 842

Output for the Sample Input 4

340340391

Sample Input 5

2 2
1 2
2 1

Output for the Sample Input 5

0

Source: ACM-ICPC Japan Alumni Group Summer Camp , Day 3 B, Tokyo, Japan, 2012-09-16
http://acm-icpc.aitea.net/