# 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

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 |

2 3 1 0 1 | 3 |