H - ダイヤグラム
Editorial
/
あなたはとある鉄道会社で,とある地区の発展を任された敏腕マネージャである.最近,地区の人口が増えてきたため,近くの路線の列車の運行本数を増やすことにした.
東西にレールが引かれたとある路線には N つの駅があり,枝分かれせずに 1 本に繋がっている.各駅には西から東に向かって順番に 駅1,駅2,... 駅Nという番号がついている.
ここで,この路線に新たに M 本の列車を導入できることになった.各列車は始発駅と終着駅が決まっており,その間を各駅停車で運行する.あなたの仕事は,駅 1 から駅 N までの各駅に,少なくとも 2 つ以上の列車が止まるように運行する列車を選ぶとき,その選び方の場合の数を答えることである.答えはとても大きくなるかもしれないので,1,000,000,007 で割った余りを答えよ.
入力は以下の形式で標準入力から与えられる.
場合の数を 1,000,000,007 で割った余りを 1 行に出力せよ.
なお、最後には改行を出力せよ.
10 点分については,入力の条件に加え,以下の条件を全て満たす.
50 点分については,入力の条件に加え,以下の条件を全て満たす.
3 つの列車のうち,2 つ以上使うことで,条件が達成できる.
与えられた列車だけでは条件を達成できない(駅 1,駅 5 に停まる列車が 1 つしかない)ため,答えは 0 通りである.
全ての列車を使うとき,以下の図のように全ての駅に列車が 2 つ以上停まるので条件を満たす.この場合,駅 4 と駅 5 の間には列車が運行しないが,気にしてはいけない.
Time Limit: 2 sec / Memory Limit: 256 MB
問題
ここで,この路線に新たに 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を満たす.
出力
なお、最後には改行を出力せよ.
部分点
- 2 ≦ N ≦ 8
- 1 ≦ M ≦ 8
50 点分については,入力の条件に加え,以下の条件を全て満たす.
- 2 ≦ N ≦ 40
- 1 ≦ M ≦ 40
入力例 1
3 3 1 3 1 3 1 3
出力例 1
4
入力例 2
5 4 1 2 2 3 3 4 4 5
出力例 2
0
入力例 3
8 4 1 4 1 4 5 8 5 8
出力例 3
1