Card Arrangement

There are N cards, each with one number written on it. The numbers are the integers from 0 to N-1, and no two cards have the same number.

Choose k cards and arrange them as C_{k-1}, C_{k-2}, ..., C_0. If this arrangement is interpreted as a base-N number, C_i is the digit in the N^i place, so the value is C_{k-1} × N^{k-1} + C_{k-2} × N^{k-2} + ... + C_0 × N^0.

The arrangement has constraints of the form C_i > C_j. This means that the number on the card placed at position i must be greater than the number on the card placed at position j. It is always true that i != j.

Given N, k, and the constraints, find the largest possible value and the smallest possible value among all valid arrangements, then output their difference.

The first line contains three integers N, k, and P: the total number of cards, the number of cards to choose, and the number of constraints.

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

Each of the next P lines contains two integers a and b. This represents the constraint C_a > C_b.

Output the difference between the largest and smallest values of valid card arrangements, modulo 1,000,000,007.

At least one valid arrangement always exists.