18226번 - 안 읽은 사람은 누구?

문제

N명이 한 채팅 프로그램에서 대화 중에 있다. 이 채팅 프로그램은 각 메시지마다 누가 보냈는지, 그 메시지를 N명 중에서 몇 명이 읽지 않았는지 알려준다.
이 채팅 프로그램은 읽지 않은 사람 수를 업데이트할 때 다음과 같은 규칙을 따른다:

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

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

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

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

의 4가지가 가능하다.

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

입력

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

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

출력

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

제한

힌트