第2回早稲田大学プログラミングコンテスト

H - ダイヤグラム


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

 あなたはとある鉄道会社で,とある地区の発展を任された敏腕マネージャである.最近,地区の人口が増えてきたため,近くの路線の列車の運行本数を増やすことにした.

問題

 東西にレールが引かれたとある路線には N つの駅があり,枝分かれせずに 1 本に繋がっている.各駅には西から東に向かって順番に 駅1,駅2,... 駅Nという番号がついている.
 ここで,この路線に新たに M 本の列車を導入できることになった.各列車は始発駅と終着駅が決まっており,その間を各駅停車で運行する.あなたの仕事は,駅 1 から駅 N までの各駅に,少なくとも 2 つ以上の列車が止まるように運行する列車を選ぶとき,その選び方の場合の数を答えることである.答えはとても大きくなるかもしれないので,1,000,000,007 で割った余りを答えよ.

入力

入力は以下の形式で標準入力から与えられる.
N M
start_{1} end_{1}
start_{2} end_{2}
...
start_{M} end_{M}
  • 1 行目には駅の数 N(2 ≦ N ≦ 100,000) と列車の数 M(1 ≦ M ≦ 200)が半角スペース区切りで与えられる.
  • 2 行目~ M+1 行目には各列車の情報,つまり始発駅 start_{i}と終着駅 end_{i} が半角スペース区切りで与えられる.
  • i について 1 ≦ start_{i} < end_{i} ≦ Nを満たす.

出力

場合の数を 1,000,000,007 で割った余りを 1 行に出力せよ.
なお、最後には改行を出力せよ.

部分点

10 点分については,入力の条件に加え,以下の条件を全て満たす.
  • 2 ≦ N ≦ 8
  • 1 ≦ M ≦ 8

50 点分については,入力の条件に加え,以下の条件を全て満たす.
  • 2 ≦ N ≦ 40
  • 1 ≦ M ≦ 40

入力例 1

3 3
1 3
1 3
1 3

出力例 1

4
3 つの列車のうち,2 つ以上使うことで,条件が達成できる.

入力例 2

5 4
1 2
2 3
3 4
4 5

出力例 2

0
与えられた列車だけでは条件を達成できない(駅 1,駅 5 に停まる列車が 1 つしかない)ため,答えは 0 通りである.

入力例 3

8 4
1 4
1 4
5 8
5 8

出力例 3

1
全ての列車を使うとき,以下の図のように全ての駅に列車が 2 つ以上停まるので条件を満たす.この場合,駅 4 と駅 5 の間には列車が運行しないが,気にしてはいけない.
図1:入力例3の駅と列車の様子

Submit提出する