H - ダイヤグラム Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

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

問題

　東西にレールが引かれたとある路線には 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の駅と列車の様子