Expected Maximum of Interval Minimums

Sol has developed a magical random number system that generates truly random numbers from environmental noise. Now, Sol generates an array \(a_1,a_2,\dots,a_n\) of \(n\) integers, where each \(a_i\) is chosen uniformly and independently at random from the range \([1,x]\).

Then, he performs \(q\) queries. In the \(i\)th query two numbers \(l_i\) and \(r_i\) are given, and the answer to the query is defined as the minimum value among \(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\), i.e. \[ m_i = \min_{l_i \le j \le r_i} a_j. \]

The final test result is the maximum among all query answers, namely \[ Y = \max_{1 \le i \le q} m_i. \]

Sol repeated the experiment many times. He now wants to know the expected value of \(Y\). Output the expected value modulo \(666623333\). All formulas are in LaTeX format.

Note: It can be shown that the expected value can be computed as \[ E[Y] = \sum_{k=1}^{x} \Pr(Y \ge k), \] where for each integer \(k\) we have \[ \Pr(Y \ge k) = 1 - \prod_{i=1}^{q} \Bigl(1 - \Bigl(\frac{x-k+1}{x}\Bigr)^{r_i-l_i+1}\Bigr). \]

inputFormat

The first line contains three integers \(n\), \(x\), and \(q\) \((1 \le n, x \le ?; 1 \le q \le ?)\) -- the length of the array, the upper bound of the range, and the number of queries.

Then \(q\) lines follow. Each of these lines contains two integers \(l_i\) and \(r_i\) \((1 \le l_i \le r_i \le n)\), representing a query.

outputFormat

Output a single integer: the expected value of the test result \(Y\) modulo \(666623333\).

sample

3 3 1
2 2

2