Cowmpetency

파머 존은 소 무리를 이끌 새 리더를 뽑고 있다. 이를 위해 지원한 소 $N$마리를 면접했다($2 \leq N \leq 10^9$). 면접을 마칠 때마다 각 소에게 $1$부터 $C$까지($1 \leq C \leq 10^4$) 사이의 정수 cowmpetency 점수를 매겼다. 이 점수는 그 소의 리더십 능력과 연관되어 있다.

파머 존은 모든 소의 cowmpetency 점수를 잊어버렸다. 다만 $Q$쌍 $(a_i, h_i)$($1 \leq Q \leq \min(N - 1, 100)$)은 기억한다. 소 $h_i$는 소 $1$번부터 $a_i$번까지의 어떤 소보다도 엄격하게 큰 cowmpetency 점수를 가진 첫 번째 소였다. 따라서 $1 \leq a_i < h_i \leq N$이다.

파머 존이 알려준 $Q$쌍으로 세어 보자. 이 정보와 일치하는 cowmpetency 점수 수열의 개수를 구하라. 적어도 하나의 수열이 존재함이 보장된다. 개수는 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

첫 줄에 $N$, $Q$, $C$가 주어진다.

다음 $Q$줄에는 각각 한 쌍 $(a_i, h_i)$가 주어진다. 모든 $a_j$는 서로 다르다.

이 정보와 일치하는 cowmpetency 점수 수열의 개수를 $10^9+7$로 나눈 나머지로 출력한다.