Problem Description

sol has developed a magical random number system that can automatically generate true random numbers based on environmental noise.

Now, sol plans to generate $n$ integers $a_1, ..., a_n$ within the range $[1, x]$, and then perform some queries.

There are $q$ queries, each with two parameters $l_i$ and $r_i$. For each query $i$, sol will calculate $\min_{l_i \leq j \leq r_i} a_j$ (the minimum value among the elements of array $a$ with indices between $l_i$ and $r_i$).

The final test result will be the maximum value obtained from these queries.

sol has conducted many experiments, and now he wants to know the expected size of the test result, modulo $666623333$.

Input Format

The first line contains three numbers $n, x, q$.

The following $q$ lines, each containing two numbers, represent $l_i$ and $r_i$.

Output Format

A single line containing one number, representing the answer.

Sample Input and Output

Sample Input #1

2 2 1
1 2

Sample Output #1

499967501

Sample Input #2

6 6 6
1 3
2 4
3 5
4 6
5 6
3 4

Sample Output #2

88571635

Notes/Hints

Hint: The result of a fraction $\frac{a}{b}$ modulo $666623333$ is $a \times b^{666623331} \mod 666623333$.

For $10\%$ of the data, $n, x, q \leq 6$.

For another $20\%$ of the data, $q = 1$.

For $50\%$ of the data, $n, x, q \leq 300$.

For $70\%$ of the data, $n, x, q \leq 800$.

For $100\%$ of the data, $1 \leq n, x, q \leq 2000$, and for each $i$, $1 \leq l_i \leq r_i \leq n$.

见题面 Input 部分

见题面 Output 部分