随机数生成器

题目描述

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

输出格式


一行一个数,表示答案。

输入输出样例

输入样例 #1

2 2 1
1 2

输出样例 #1

499967501

输入样例 #2

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

输出样例 #2

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