Sum of Products of Restricted Sequences

You are given a positive integer sequence A of length m such that every element satisfies \(1 \leq A_i \leq n\). Additionally, there are some restrictions of the form \(A_x \neq y\) which specify that at position \(x\), the value \(y\) is not allowed.

Let the product of a sequence \(A\) be defined as \(\prod_{i=1}^{m} A_i\). Your task is to compute the sum of the products over all valid sequences. In other words, if \(S\) is the set of all valid sequences then you need to find:

[ \sum_{T \in S} \prod T ]

Output the answer modulo (10^9+7).

Hint: Since the choices for each position are independent, you can compute the contribution of each position separately.

inputFormat

The first line contains three integers \(m\), \(n\), and \(k\), representing the length of the sequence, the maximum value for each element, and the number of restrictions respectively.

Each of the next \(k\) lines contains two integers \(x\) and \(y\) (1-indexed), indicating that at position \(x\), the value \(y\) is forbidden.

outputFormat

Output a single integer --- the sum of products of all valid sequences, taken modulo \(10^9+7\).

sample

2 2 0

9