题目描述

sol 研发了一个神奇的随机数系统，可以自动按照环境噪音生成真·随机数。

现在 sol 打算生成 $n$ 个 $[1,x]$ 的整数 $a_1, ..., a_n$，然后进行一些询问。

$q$ 次询问，每次询问 $i$ 有两个参数 $l_i$ 和 $r_i$，sol 会计算 $\min_{l_i \leq j \leq r_i} a_j$（$a$ 数组中下标在 $l_i, r_i$ 之间的数的最小值）。

最后测试结果会是这些询问得到的结果的最大值。

sol 进行了很多次实验，现在他想问问你测试结果的期望大小是多少，对 $666623333$ 取模。

输入格式

第一行三个数 $n, x, q$。

下面 $q$ 行，第 $i$ 行两个数表示 $l_i$ 和 $r_i$。

输出格式

一行一个数，表示答案。

2 2 1
1 2

499967501

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

88571635

提示

提示：一个分数 $\frac{a}{b}$ 对 $666623333$ 取模的结果为 $a\times b^{666623331}~\mod~666623333$。

对于 $10\%$ 的数据，$n,x,q \leq 6$。

对于另外 $20\%$ 的数据，$q=1$。

对于 $50\%$ 的数据，$n,x,q \leq 300$。

对于 $70\%$ 的数据，$n,x,q \leq 800$。

对于 $100\%$ 的数据，$1 \leq n,x,q \leq 2000$，对于每个 $i$，$1 \leq l_i \leq r_i \leq n$。