Counting Leadership Score Sequences

Farmer John is hiring a new herd leader among his $N$ cows. In the interview process, each cow is assigned a leadership score $c_i$ from (1) to (C) (inclusive). Unfortunately, after interviewing all (N) cows, Farmer John has forgotten all the scores. However, he still remembers (Q) pairs ((a_i, h_i)). Each pair ((a_i, h_i)) means that if you look at cows (1,2,\dots,a_i), let (M = \max{c_1, c_2, \dots, c_{a_i}}), then among cows with indices greater than (a_i), the first cow whose score is strictly greater than (M) is the cow with index (h_i). In other words, (h_i) is the smallest index (j) (with (a_i < j \le N)) such that (c_j > M).

Your task is to count the number of sequences (c_1, c_2, \dots, c_N) with each (c_i) in ([1,C]) that are consistent with all the (Q) constraints. It is guaranteed that there is at least one valid sequence. Since the answer may be very large, output it modulo (10^9+7).

inputFormat

The first line contains three integers (N), (C) and (Q) (with (2 \le N \le 10^9), (1 \le C \le 10^4) and (1 \le Q \le \min(N-1,100))).

Then (Q) lines follow, each containing two integers (a_i) and (h_i) (with (1 \le a_i < h_i \le N)). For each pair, if we let (M = \max{c_1, c_2, \dots, c_{a_i}}), then (h_i) is the index of the first cow among indices (a_i+1, a_i+2, \dots, N) such that (c_{h_i} > M).

outputFormat

Output a single integer, which is the number of valid leadership score sequences modulo (10^9+7).

sample

5 3 1
2 4

13