#P3600. 随机数生成器

    ID: 4865 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划,dp洛谷原创O2优化期望洛谷月赛

随机数生成器

题目描述

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

现在 sol 打算生成 nn[1,x][1,x] 的整数 a1,...,ana_1, ..., a_n,然后进行一些询问。

qq 次询问,每次询问 ii 有两个参数 lil_irir_i,sol 会计算 minlijriaj\min_{l_i \leq j \leq r_i} a_jaa 数组中下标在 li,ril_i, r_i 之间的数的最小值)。

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

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

输入格式

第一行三个数 n,x,qn, x, q

下面 qq 行,第 ii 行两个数表示 lil_irir_i

输出格式

一行一个数,表示答案。

2 2 1
1 2
499967501
6 6 6
1 3
2 4
3 5
4 6
5 6
3 4
88571635

提示

提示:一个分数 ab\frac{a}{b}666623333666623333 取模的结果为 a×b666623331 mod 666623333a\times b^{666623331}~\mod~666623333

对于 10%10\% 的数据,n,x,q6n,x,q \leq 6

对于另外 20%20\% 的数据,q=1q=1

对于 50%50\% 的数据,n,x,q300n,x,q \leq 300

对于 70%70\% 的数据,n,x,q800n,x,q \leq 800

对于 100%100\% 的数据,1n,x,q20001 \leq n,x,q \leq 2000,对于每个 ii1lirin1 \leq l_i \leq r_i \leq n