안 읽은 사람은 누구?

$N$명이 한 채팅 프로그램에서 대화 중이다. 이 채팅 프로그램은 메시지마다 누가 보냈는지, 그 메시지를 $N$명 중 몇 명이 읽지 않았는지 알려준다.

이 채팅 프로그램은 읽지 않은 사람 수를 업데이트할 때 다음 규칙을 따른다.

1. 한 번 프로그램에 접속하면 그동안 읽지 않았던 모든 메시지와 접속한 이후 접속을 종료하기 전까지 올라온 모든 메시지를 읽은 것으로 간주한다.
2. 메시지를 보낸 사람은 그 메시지와 그 이전의 모든 메시지를 모두 읽은 것으로 간주한다.

호준이는 모든 메시지의 발신자와 읽지 않은 사람 수를 알고 있다. 호준이는 각 사람이 어디부터 메시지를 읽지 않았는지 따져 보고, 가능한 경우의 수가 몇 가지인지 알아보려고 한다. 두 경우가 다르다는 것은 어떤 메시지에 대해 그 메시지를 읽은 사람의 집합이 두 경우에서 다르다는 뜻이다.

예를 들어 이 채팅 프로그램에 4명이 참여 중이고, 차례대로 두 개의 메시지를 각각 1번, 2번 사람이 보냈으며, 각각 1명, 2명이 읽지 않았다고 하면 다음 4가지가 가능하다.

• 첫 번째 메시지를 읽지 않은 사람 = 3번 사람, 두 번째 메시지를 읽지 않은 사람 = 1번 사람과 3번 사람
• 첫 번째 메시지를 읽지 않은 사람 = 3번 사람, 두 번째 메시지를 읽지 않은 사람 = 3번 사람과 4번 사람
• 첫 번째 메시지를 읽지 않은 사람 = 4번 사람, 두 번째 메시지를 읽지 않은 사람 = 1번 사람과 4번 사람
• 첫 번째 메시지를 읽지 않은 사람 = 4번 사람, 두 번째 메시지를 읽지 않은 사람 = 3번 사람과 4번 사람

호준이는 경우의 수가 매우 큰 값이 나올 수 있다는 것을 깨달았고, 경우의 수를 $10^9+7$로 나눈 나머지를 구하려고 한다. 호준이를 도와주자.

첫 번째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 입력된다. ($1 \le N \le 100,000$, $1 \le M \le 1,000,000$)

두 번째 줄부터 $M$개의 줄에 걸쳐 각 메시지에 대한 정보인 두 정수 $a$, $b$가 공백으로 구분되어 입력된다. 메시지는 시간 순서대로 주어지며, 생략된 메시지는 없다고 가정한다. $a$는 이 메시지를 보낸 사람, $b$는 이 메시지를 읽지 않은 사람 수를 나타낸다. ($1 \le a \le N$, $0 \le b < N$)

첫 번째 줄에 누가 읽지 않았는지 가능한 경우의 수를 $10^9+7$로 나눈 나머지를 출력하라.