카드 배열

숫자가 하나씩 적힌 카드가 N장 있다. 각 카드의 숫자는 0 이상 N-1 이하이고, 모든 숫자는 서로 다르다.

이 중 k장을 골라 순서대로 놓은 것을 C_{k-1}, C_{k-2}, ..., C_0이라고 하자. 이 배열을 N진법 수로 보면 C_i는 N^i 자리의 숫자이며, 전체 값은 C_{k-1} × N^{k-1} + C_{k-2} × N^{k-2} + ... + C_0 × N^0 이다.

카드 배열에는 C_i > C_j 형태의 제약조건이 주어진다. 이는 i번째 자리에 놓인 카드의 숫자 C_i가 j번째 자리에 놓인 카드의 숫자 C_j보다 커야 한다는 뜻이다. 항상 i != j이다.

N, k, 제약조건이 주어질 때, 모든 제약조건을 만족하는 카드 배열 중 값이 가장 큰 배열과 가장 작은 배열을 찾고, 두 값의 차이를 구하라.

첫째 줄에 전체 카드 수 N, 선택할 카드 수 k, 제약조건 수 P가 공백으로 구분되어 주어진다.

3 ≤ k ≤ N ≤ 300,000, 0 ≤ P ≤ 1,000,000

다음 P개 줄에는 두 정수 a, b가 공백으로 구분되어 주어진다. 이는 C_a > C_b 제약조건을 뜻한다.

제약조건을 만족하는 카드 배열 중 값이 가장 큰 배열의 값과 가장 작은 배열의 값의 차이를 1,000,000,007로 나눈 나머지를 출력한다.

제약조건을 만족하는 카드 배열은 항상 하나 이상 존재한다.