Nested Palindromes

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

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).

Output

Print the number of strings possible according to the above constraints. As the answer can be big, print it modulo 1000000007.

Samples

Input	Output
3 2 1 0 2	4

Input	Output
2 3 1 0 1	3