忍者少女は止まらない

ミチル

お屋敷の中は格子状になっています。イズナが描いた下の図のように、上から $i$ 行目は $1$ 列目から $i-1$ 列目までが正方形のマスで、$i$ 列目が直角二等辺三角形のマスです！各マスの辺の長さは、直角二等辺三角形の斜辺を除いて、すべて $1$ です！

• 下降（↓）：下へ一マス移動する。現在位置が $(x, y)$ なら、点 $(x, y - 1)$ へ移動する。
• 回避（→）：右へ一マス移動する。現在位置が $(x, y)$ なら、点 $(x + 1, y)$ へ移動する。

すると……移動回数がちょうど $N$ 回の経路だけを考えることになりますね！また、お屋敷の外へ出てはいけないので、移動中は常に辺を含む三角形の内側にいなければなりません。

ところが、お屋敷には恐ろしい罠があるのです！イズナが集めた情報によると、移動中に次の条件をすべて満たす必要があるそうです！

• $1 \le i \le M$ に対し、$k_i$ 回目の移動ではイズナのいる位置で罠が作動するため、罠を避けるべく $c_i$ 回目の回避（→）を行わなければならない。

つまり、$k_i$ 回目の移動は必ず回避（→）であり、それが経路全体で必ず $c_i$ 回目の回避（→）でなければならないのです！もちろん、イズナは忍者ですから、罠がなくても回避（→）できます！

お屋敷にはゴールへ続く分かれ道がたくさんありますから、条件を満たすすべての経路を把握することが大切です！イズナが選べる経路は何通りあるか、求めましょう！ニンニン！

続く $M$ 行には、それぞれ $k_i$, $c_i$ が空白区切りで与えられる。$(1 \le k_i \le N$; $k_i < k_{i + 1}$; $1 \le c_i \le \frac{N}{2}$; $c_i < c_{i + 1})$

実行時間制限

1000 ms

メモリ制限

1024 MB

チェッカー

CUSTOM