P3600 Random Number Generator

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

The first line contains three integers $n, x, q$. Each of the next $q$ lines contains two integers $l_i$ and $r_i$.

Output a single integer, the answer.

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