Description

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

Now sol plans to generate $n$ integers in $[1,x]$, namely $a_1, ..., a_n$, and then handle some queries.

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

Finally, the test result is the maximum among the results of these queries.

sol has conducted many experiments. Now he wants to ask you for the expected value of the test result, modulo $666623333$.

Input Format

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

Each of the next $q$ lines contains two integers $l_i$ and $r_i$.

Output Format

Output a single integer, the answer.

2 2 1
1 2

499967501

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

88571635

Hint

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

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

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

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

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

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

Translated by ChatGPT 5