MinimumCostPath

NxNの方眼がある。

(N=3の場合の図)

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

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

N M
X1 Y1
X2 Y2
……
XM YM

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

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

• 2 ≤ N ≤ 106

• 0 ≤ M ≤ 50

• 1 ≤ Xi , Yi ≤ N

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

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

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