You will be given the length of a string N and the size of the character set allowed for the string K. Also you will be provided with M demands in the format x y (0 ≤ x ≤ y < N), meaning substring from x to y inclusive needs to be a palindrome. Now your job is to count the number of possible strings of length N, the size of the character set K and M demands for palindromic substrings.
Input begins with three integers N, K, M (1 ≤ N, K, M ≤ 10000) representing the length of the string, size of the character set and the number of demands. Next M lines each contains two integers x and y (0 ≤ x ≤ y < N).
Print the number of strings possible according to the above constraints. As the answer can be big, print it modulo 1000000007.
| Input | Output |
|---|---|
3 2 1 0 2 | 4 |
| Input | Output |
|---|---|
2 3 1 0 1 | 3 |