Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Nested Palindromes

Limits: 1s, 512 MB

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

InputOutput
3 2 1
0 2
4
2 3 1
0 1
3

Discussion
Submit

Login to submit