시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB93921514321.966%

문제

하나의 숫자가 쓰여 있는 카드가 N장이 있다. 쓰여 있는 숫자는 0부터 N-1 사이의 숫자 중 하나이며, 모든 카드의 숫자는 서로 다르다. 

이 카드들 중에서 k개의 카드를 선택하여 배열한 순서를 Ck-1, Ck-2, ..., C0 라고 하자. 이렇게 배열된 k장의 카드가 N진법의 수를 나타낸다고 하면, 카드 Ci는 N진법의 수에서의 한 자리수를 의미하며 그 자릿수의 값은 Ci*Ni이다. 그러므로 배열된 카드의 수의 값은 Ck-1×Nk-1 + Ck-2×Nk-2 + ... + C0×N0이 된다.

배열되는 카드들 사이에는 C> Cj 형태의 제약조건이 주어진다. 제약조건  C> Cj는  Ci 숫자가  Cj 숫자보다 커야함을 의미한다. 단, i != j.

예를 들어, N=4, K=3인 경우에 C2 > C0, C0 > C1의 제약조건이 주어졌다고 하자. 이 경우 가능한 카드의 배열은 (2, 0, 1), (3, 1, 2), (3, 0, 1), 그리고 (3, 0, 2) 네 가지 경우가 있다. 

이 네 개의 경우들 중에서 가장 큰 수가 되는 카드의 배열은 (3, 1, 2)이고 이 수의 값은 3*42 + 1*41 + 2 = 54 이다. 또한, 가장 작은 수가 되는 카드 배열은 (2, 0, 1)이고 이 수의 값은 2×42 + 0×41 + 1 = 33이다.

전체 카드의 수와 선택할 카드의 수 그리고 제약조건들이 주어질 때, 제약조건을 만족하는 카드배열 중에서 가장 큰 값을 갖는 카드배열과 가장 작은 값을 갖는 카드배열을 찾아서 그 값의 차이를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 전체 카드의 수를 나타내는 N과 선택하는 카드의 수 k와 제약조건의 수 P가 하나의 빈칸을 사이에 두고 주어진다. 단, 3 ≤ k ≤ N ≤ 300,000, 0 ≤ P ≤ 1,000,000이다. 두 번째 줄부터 P개의 줄에는 각 줄마다 하나의 제약조건을 나타내는 두 개의 정수 a, b가 하나의 빈칸을 사이에 두고 주어진다. 이는 제약조건 Ca > Cb를 의미한다.

출력

제약조건을 만족하는 카드배열 중에서 가장 큰 값을 갖는 카드배열과 가장 작은 값을 갖는 카드배열을 찾고, 그 값의 차이를 1,000,000,007로 나눈 나머지를 출력한다. 단, 제약조건을 만족하는 카드의 배열이 존재하지 않는 경우는 없다.

예제 입력 1

4 3 2
2 0
0 1

예제 출력 1

21