🐷大肚肚
CF-101B3

上学

2.0s💾 265MB

📋 题目描述

一条平直的公路上设置了 n+1n+1 个公交车站,编号从 00nn ,其中 00 号公交车站旁是胖球肚的家, nn 号公交车站旁是胖球肚每天要去的学校。从胖球肚的家到学校有 mm 辆公交车,第 ii 辆公交车从站点 sis_i 开往站点 tit_isi<tis_i<t_i ),胖球肚上学乘坐任何一辆公交车都只能在该车的终点站下车,上学过程中既不能步行,也不能逆行。你的任务是帮助胖球肚计算她上学有多少种不同的乘车方案。

📥 输入格式

第一行包含两个整数 nnmm ( 1n1091 ≤ n ≤ 10^9 , 0m1050 ≤ m ≤ 10^5 )。接下来的 mm 行,每行包含两个整数 sis_i, tit_i ,分别代表一辆巴士的起始站和终点站的编号 ( 0si<tin0 ≤ s_i < t_i ≤ n ) 。

📤 输出格式

仅有一个数,表示可以到达的学校的数量,结果对 109+710^9+7

💡 提示

第一项测试的唯一路线是:先搭乘1号公交车到1号公交车站,然后换乘2号公交车到2号公交车站。

在第二项测试中,没有公交车行驶到学校所在的第三个公交车站。因此,正确答案是0

在第三项测试中,杰拉德可以选择乘坐或不乘坐前四辆公交车来接近学校。因此,正确答案是24 = 16

📝 样例 1

输入
2 2
0 1
1 2
输出
1

📝 样例 2

输入
3 2
0 1
1 2
输出
0

📝 样例 3

输入
5 5
0 1
0 2
0 3
0 4
0 5
输出
16

📚 来源

💡 题目讲解

1

理解题意

仔细阅读题目描述,明确输入输出要求和约束条件。把题目用自己的话复述一遍,确保理解无误。

1 / 4