小男孩杰拉德在离他家很远的学校学习。这就是为什么他每天都要乘公共汽车去那里。从家到学校的路用一段直线表示;该路段恰好包含 n + 1 个公交车站。所有这些都按照从杰拉尔德家出来的顺序用从 0 到 n 的整数进行编号。 Gerald 家附近的公交车站编号为 0,学校附近的公交车站编号为 n。
有 m 辆公交车在房子和学校之间运行:第 i 辆公交车从车站 si 开往 ti (si < ti),按照其在路段上的顺序访问所有中间车站。此外,杰拉德也不是白痴,除非还有可能乘坐离学校更近的地方,否则他不会下车(显然,下车是完全没有意义的)。换句话说,Gerald 可以在编号为 si 到 ti - 1(含)的任何车站上车 i 辆公交车,但他只能在 ti 公交车站下车。
Gerald 无法在公交车站之间行走,也无法沿着从学校到家的方向移动。
Gerald 想知道他从家到学校有多少种方式。告诉他这个号码。如果杰拉德在不同公交车的车站之间穿过某些路段,则两种方式被认为是不同的。由于路数可能太多,请求该数除以 1000000007 (109 + 7) 的余数。
输入
第一行包含两个以空格分隔的整数:n 和 m (1 ≤ n ≤ 109, 0 ≤ m ≤ 105)。然后跟随 m 行,每行包含两个整数 si、ti。它们是公交车的起点站和终点站的数量(0 ≤ si < ti ≤ n)。
输出
打印唯一的数字 — 到达学校的方式数模 1000000007 (109 + 7)。
示例
输入 #1
2 2 0 1 1 2
输出 #1
1
输入 #2
3 2 0 1 1 2
输出 #2
0
输入 #3
5 5 0 1 0 2 0 3 0 4 0 5
输出 #3
16
注意
第一次测试有唯一的到达学校的变体:首先乘坐一号巴士到一号巴士站;然后乘坐二号巴士到二号巴士站。
在第二次测试中,没有巴士前往学校所在的第三个巴士站。因此,正确答案是0。
在第三次测试中,杰拉德可以选择乘坐或不乘坐前四辆巴士中的任何一辆来接近学校。因此,正确答案是 24 = 16。