問題
在这里,我们将为此路线添加一条新线路。 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
图 1:输入示例 3 中的车站和列车