AT_wupc_08 ダイヤグラム

[problemUrl]: https://atcoder.jp/contests/wupc2nd/tasks/wupc_08 あなたはとある鉄道会社で，とある地区の発展を任された敏腕マネージャである．最近，地区の人口が増えてきたため，近くの路線の列車の運行本数を増やすことにした． 東西にレールが引かれたとある路線には $ 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}\ を満たす． $ 場合の数を $ 1,000,000,007 $ で割った余りを $ 1 $ 行に出力せよ． なお、最後には改行を出力せよ． $ 10 $ 点分については，入力の条件に加え，以下の条件を全て満たす． - $ 2\ ≦\ N\ ≦\ 8 $ - $ 1\ ≦\ M\ ≦\ 8 $ $ 50 $ 点分については，入力の条件に加え，以下の条件を全て満たす． - $ 2\ ≦\ N\ ≦\ 40 $ - $ 1\ ≦\ M\ ≦\ 40 $ ```

3 3
1 3
1 3
1 3
```

 ```
4
```

 ```
5 4
1 2
2 3
3 4
4 5
```

 ```
0
```

 ```
8 4
1 4
1 4
5 8
5 8
```

 ```
1
```
                            

N/A

N/A