P10105: 上学路线

---

【题目描述】

【题目描述】
小男孩小智在离他家很远的学校上学。那就是他每天必须乘公共汽车去那里的原因。从家到学校的路用一段直线来表示;该段恰好包含n+1个公交车站。所有的东西都用从0到n的整数编号，按照他们从小智家开始的顺序。小智家附近的公交车站是0号，学校附近的公交车站是n号。
在房子和学校之间有m辆公共汽车:第i辆公共汽车从si站到ti站(si<ti)，按照它们在该段上的顺序访问所有中间站点。此外，小智不是傻瓜，他不会下车，直到它仍然可以乘坐它靠近学校(显然，下车是完全没有意义的)。换句话说，小智可以在编号为si到ti-1的任何站点上乘坐第i路公共汽车，但他只能在第i路公共汽车站点下车。
小智不能在公交车站之间行走，也不能从学校走到家里。
小智想知道他从家到学校有多少条路。告诉他这个号码。如果小智穿过不同公共汽车站点之间的某个路段，则认为两条路是不同的。由于方法的数量可能太多，请找出这个数除以1000000007(10⁹+7)的余数。
【输入格式】
第一行包含两个空格分隔的整数n和m(1≤n≤10⁹,0≤m≤10⁵)。然后跟随m行，每一行包含两个整数si,ti。分别为公交车的起止站个数(0≤si<ti≤n)。
【输出格式】
打印唯一的数字-到学校的路数模1000000007(10⁹+7)。
【样例输入一】
2 2
0 1
1 2
【样例输出一】
1
【样例输入二】
3 2
0 1
1 2
【样例输出二】
0
【样例输入三】
5 5
0 1
0 2
0 3
0 4
0 5
【样例输出三】
16
【样例说明】
第一个测试有唯一的变体去学校:首先乘1路公共汽车到1号公共汽车站;然后乘2路公共汽车到2号公共汽车站。
在第二次测试中，没有公共汽车到达学校所在的第三个公共汽车站。因此，正确答案是0。
在第三次测试中，小智可以选择乘坐或不乘坐前四辆公交车中的任何一辆，以便更接近学校。因此，正确答案是2⁴=16。

题目类型~

贪心 

咻咻~

提交答案 状态 返回