정올이는 하마들을 위한 새로운 대장을 선택하고 있다. 이를 위해 그는 N마리의 하마를 인터뷰했다. 각 인터뷰 후, 그는 후보자에게 1부터 C사이의 정수로 "하마 능력치" 점수를 부여했는데, 이는 리더십 능력과 관련이 있다.

정올이는 많은 하마를 인터뷰했기 때문에 모든 하마의 능력치 점수를 잊어버렸다. 하지만 그는 Q 쌍의 숫자 (a_i, h_i)를 기억하고 있다. 여기서 하마 h_i는 1부터 a_i까지의 하마들보다 점수가 첫 번째로 더 높은 하마다 (따라서 1≤a_i<h_i≤N).

Q 쌍의 (a_i, h_i)를 바탕으로 정올이가 얼마나 많은 점수 시퀀스를 선택할 수 있는지 계산해 보자! 최소한 하나의 가능한 시퀀스가 존재하는 것이 보장된다. 이 숫자는 매우 클 수 있으므로 10^9+7로 나눈 값을 출력하라.

하마 대장 timer 2s memory 1024MB

하마 대장 2s 1024MB