← 返回题目列表

AtCoder · wupc_08

H. 图

中文机器翻译题面 查看原题
 你是一家铁路公司的才华横溢的经理,受托负责某个地区的发展。最近,随着该地区人口的增加,我们决定增加附近路线的列车班次。

問題

 在某条铁轨从东向西拉的路线上, 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 满足条件,因为它至少停止了 3 次。在这种情况下,车站 4 和车站 5 期间没有火车运行,但不用担心。
图 1:输入示例 3 中的车站和列车