题目描述

给定长度为 $ n $ 的序列：$ a_1, a_2, \cdots , an $，记为 $ a[1 \colon n] $。类似地，$ a[l \colon r] $（$ 1 \leq l \leq r \leq n$）是指序列：$ a{l}, a{l+1}, \cdots ,a{r-1}, a_r $。若 $1\leq l \leq s \leq t \leq r \leq n$，则称 $ a[s \colon t] $是 $ a[l \colon r] $ 的子序列。

现在有 $ q $ 个询问，每个询问给定两个数 $ l $ 和 $ r $，$ 1 \leq l \leq r \leq n $，求 $ a[l \colon r] $ 的不同子序列的最小值之和。例如，给定序列 $ 5, 2, 4, 1, 3 $，询问给定的两个数为 $ 1 $ 和 $ 3 $，那么 $ a[1 \colon 3] $ 有 $ 6 $ 个子序列 $a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3] $，这 $6 $ 个子序列的最小值之和为 $5+2+4+2+2+2=17$。

输入格式

输入文件的第一行包含两个整数 $ n $ 和 $ q $，分别代表序列长度和询问数。

接下来一行，包含 $ n $ 个整数，以空格隔开，第 $ i $ 个整数为 $ a_i $，即序列第 $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;
}

其中 $\text{lastAns}$ 表示上次询问的答案，第一个询问 $\text{lastAns}$ 为 $0$。

每次询问时的调用方法为：

l = rnd() % n + 1, r = rnd() % n + 1;
if (l > r) std::swap(l, r);

输出格式

输出共一行一个整数，表示所有询问的答案之和模 $1000000007$ 的值。

由于本题数据规模极大，直接输入输出会占用比计算多数倍的时间，因此对询问的输入输出进行了压缩。

输出压缩方法是：输出所有询问的答案之和模 $1000000007$ 的值。

样例 1

input

4 9
-216942799 -383604709 -171536855 -527908982
2307368 41 7882044 45000701

output

480963324

样例 2

input

5 8
-241312314 -489291255 -247844393 -39976393 -333832198
26228886 3 3541696 45000847

output

37657340

数据范围与提示

对于所有数据，$ 1 \leq n \leq 100000 ,1\leq q \leq 10^7,|a_i| \leq 10^9$，保证 $0\leq A<P,0\leq C<2^{31}-1,P(B+1)<2^{31}-1$。