题目描述

给定长度为 $n$ 的序列：$a_1, a_2, \cdots , a_n$，记为 $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

输入

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

输出

480963324

---

样例 2

输入

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

输出

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$