题目描述
给定长度为 n 的序列:a1,a2,⋯,an,记为 a[1:n]。类似地,a[l:r](1≤l≤r≤n)是指序列:al,al+1,⋯,ar−1,ar。若 1≤l≤s≤t≤r≤n,则称 a[s:t]是 a[l:r] 的子序列。
现在有 q 个询问,每个询问给定两个数 l 和 r,1≤l≤r≤n,求 a[l:r] 的不同子序列的最小值之和。例如,给定序列
5,2,4,1,3,询问给定的两个数为 1 和 3,那么 a[1:3] 有 6 个子序列 a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3],这 6 个子序列的最小值之和为 5+2+4+2+2+2=17。
输入格式
输入文件的第一行包含两个整数 n 和 q,分别代表序列长度和询问数。
接下来一行,包含 n 个整数,以空格隔开,第 i 个整数为 ai,即序列第 i 个元素的值。
接下来一行四个整数 A,B,C,P 表示询问的生成方式。
由于本题数据规模极大,直接输入输出会占用比计算多数倍的时间,因此对询问的输入输出进行了压缩。
输入压缩方法是:读入 4 个整数 A,B,C,P,每次询问调用以下函数生成 l 和 r:
int A, B, C, P;
long long lastAns;
inline int rnd() {
return A = (A * B + (C ^ (int)(lastAns & 0x7fffffffLL)) % P) % P;
}
其中 lastAns 表示上次询问的答案,第一个询问 lastAns 为 0。
每次询问时的调用方法为:
l = rnd() % n + 1, r = rnd() % n + 1;
if (l > r) std::swap(l, r);
输出格式
输出共一行一个整数,表示所有询问的答案之和模 1000000007 的值。
由于本题数据规模极大,直接输入输出会占用比计算多数倍的时间,因此对询问的输入输出进行了压缩。
输出压缩方法是:输出所有询问的答案之和模 1000000007 的值。
样例 1
4 9
-216942799 -383604709 -171536855 -527908982
2307368 41 7882044 45000701
480963324
5 8
-241312314 -489291255 -247844393 -39976393 -333832198
26228886 3 3541696 45000847
37657340
数据范围与提示
对于所有数据,1≤n≤100000,1≤q≤107,∣ai∣≤109,保证 0≤A<P,0≤C<231−1,P(B+1)<231−1。