[5. 버스정류장]

문제)

승용이가 다니는 학교는 승용이의 집과 거리가 꽤 멀기 때문에 승용이는 버스들을 타고 등교해야한다.
편의상 승용이의 집과 학교를 수직선 상에 놓자. 수직선의 길이는 N이고 N+1개의 버스정류장들이 있다.
버스정류장들은 0번부터 N번까지 왼쪽에서부터 오른쪽가지 연속적이게 번호가 매겨져있다.
그리고 승용이의 집 바로 앞에는 0번 정류장이 있고, 학교 바로 앞에는 N번 정류장이 있다.

이 수직선 위를 운행하는 버스는 M개의 종류가 있다. i번 버스는 S_i에서 시작해 T_i까지 모든 정류장들을 방문하며 운행한다. (단, S_i ＜ T_i)
승용이는 바보가 아니라서 버스 운행 도중에 내리지 않는다. 왜냐하면 도중에 내리는게 이득이 되는 경우가 없기 때문이다.
하지만 승용이는 운행하는 버스에 탑승하기는 한다.
즉, S_i부터 T_i-1번 정류장까지 i번 버스를 탑승할 수 있고, i번 버스를 탑승하면 반드시 T_i에서 내려야한다.

승용이는 운동을 싫어해 버스 정류장 사이를 걷지 않는다.

승용이는 자기가 집에서 출발해 학교까지가는 서로 다른 경로의 수를 구하고 싶어졌다.
도중에 한번이라도 종류가 다른 버스를 타면 서로 다른 경우로 간주된다.
경우의 수가 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 구하자.

입력 형식)

첫 줄에 정수 N, M이 주어진다. (1 ≤ N ≤ 10⁹, 0 ≤ M ≤ 10⁵)
다음 M 줄 동안 i+1번째 줄에는 i번 버스에 대한 정보 S_i와 T_i가 주어진다.
i번 버스는 Si번 정류장부터 Ti번 정류장까지 사이에 있는 정류장들을 다 방문하면서 운행한다. (0 ≤ S_i ＜ T_i ≤ N)

출력 형식)

승용이가 0번 정류장에서 출발해 N번 정류장가지 도착할 수 있는 경로의 서로 다른 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

입력 예제 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

출처:koi4u 2011 8 월 모의고사