D - マシュマロ(Marshmallow) Editorial /

Time Limit: 1 sec / Memory Limit: 256 MB

問題文

kagamizは, ペットのミズゴロウと毎日家から K m 離れた公園まで散歩をしている.
このとき, kagamizは往路と復路で, ミズゴロウと次のようなゲームをする:

  • 1 m 先か 2 m 先にマシュマロを投げ, ミズゴロウがそのマシュマロをキャッチする.
  • 投げた先にkagamizも移動し, 同じ操作を繰り返す.

ただし, このときに, 公園より後の地点や, 家より前の地点にマシュマロを投げることは許されない.
また, 往路でのスタート地点は 家から 0 mの地点, 復路でのスタート地点は 家から K mの地点であり, ここには必ず訪れることとなる.
しかし, 往路のうち P 個の地点, 復路のうち Q 個の地点, 合計 R 個の地点には水たまりがあり, せっかくのマシュマロが濡れてしまい, ミズゴロウが水たまりで遊ぶためそこから動かなくなってしまう.
したがって, 水たまりがある地点にマシュマロを投げることはしない.

このとき, kagamizとミズゴロウが, 全ての地点にマシュマロを投げ散歩をする方法は何通りあるだろうか.

あなたの仕事は, K , R , および水たまりができる地点の情報が与えられるとき, K m ある地点すべてにマシュマロを投げて, 散歩をする方法の数を 100000 で割ったあまりを kagamizに教えてあげることである.

入力

K R
t_1 a_1
t_2 a_2
.
.
.
t_R a_R
  • 1 行目には, 整数 K , R が空白を区切りとして書かれている.
  • 続く R 行には, 水たまりの情報が書かれている.
    i + 1 行目 (1 ≦ i ≦ R) には, 1, 2 のいずれかの整数の後に, 整数 a_i が空白区切りで書かれている.
    i + 1 行目の最初の数が 1 (t_i = 1) であるとき, 往路の家から a_i m離れた場所に水たまりがあることを示し,
    i + 1 行目の最初の数が 2 (t_i = 2) であるとき, 復路の家から a_i m離れた場所に水たまりがあることを示す.

出力

与えられた条件のもと, 散歩をする方法の数を, 100000 で割った余りを出力せよ.

制約

  • 1 ≦ K ≦ 3000000　家から公園までの距離
  • 0 ≦ R ≦ 100000　往路または復路にある水たまりの個数の総数
  • 1 ≦ a_i ≦ K 　家から水たまりがある地点までの距離
  • 往路か復路を表す整数 t_i は, 必ず 1,2 のいずれかである.

部分点

配点の 30% 分については, R = 0 を満たす.
配点の 20% 分については, K ≦ 15 を満たす.
配点の 10% 分については, これら 2 つの条件を両方満たす.
配点の 40% 分については, これら 2 つの条件の少なくとも一方を満たす.
※30%+20%+10%+40%=100%という意味ではないことに注意せよ.

入力例 1

3 0

出力例 1

7

入力例 2

14 2
1 9
2 3

出力例 2

7105

入力例 3

1 1
2 1

出力例 3

0
復路の出発点は必ず K mの地点であることに注意せよ.

入力例 4

3 2
1 1
2 1

出力例 4

0
この入出力例では, 家から 1 m 離れている地点に, 往路・復路ともに水たまりがある.
したがって, すべての地点に訪れる事ができないので, 0 を出力する.
(Story) kagamiz
(Problem) kagamiz
(Tester) fura2