克拉克有一个长度为 $n$ 的数列 $\left\{a_1,a_2,\dots,a_n\right\}$。对这个数列，克拉克会进行 $q$ 次询问。每一次询问他都会从数列取出一个子串；对于这个子串，他想知道这个子串的最长上升子序列是多长。
子串是指数列中连续的一部分构成的数列。我们用参数 $l,r$ 来表示子串 $\left\{a_l,a_{l+1},\dots,a_r\right\}$。
子序列是指数列中抽取若干个元素，按照原数列的顺序排列得到的新数列。例如 $\left\{a_3,a_4,a_6,a_8\right\}$ 就是数列 $\left\{a_2,a_3,a_4,a_5,a_6,a_7,a_8\right\}$ 的一个子序列。
上升数列是指除第一个元素外，其他每个元素都比前一个元素严格更大的数列。例如 $\left\{2,3,5,8\right\}$ 就是一个上升序列，而 $\left\{2,3,5,5\right\}$ 不是。
数列的长度是指数列的元素个数。
最长上升子序列是指一个数列所有可能的子序列中，是上升数列的最长的一个或若干个。
输入格式
第一行包含三个非负整数 $n,q,v$ 表示数列的长度，询问的个数和是否强制在线。其中 $v\in \{0,1\}$，分别表示不强制在线和强制在线。
接下来一行 $n$ 个正整数表示数列 $\left\{a_1,a_2,\dots,a_n\right\}$。对于 $1 \le i \le n$，保证 $1 \le a_i \le 1000$。
接下来一行，包含 $8$ 个整数 $A,B,C,D,E,F,x_0, y_0$，表示生成询问的一些参数，保证 $1 \le A,B,C,D,E,F,x_0, y_0 \le n$。
对于 $1\le i \le q$，我们用这样的方式给出每组询问的子串：首先设 $s_i$ 为第 $i$ 个询问的答案，也就是最长上升子序列的长度；并设 $s_0=0$。然后令 $$ x_i=Ax_{i-1}+By_{i-1}+C $$
$$ y_i=Dx_{i-1}+Ey_{i-1}+F $$
$$ l_i=\min\left\{\left(x_i+vs_{i-1}-1\right)\bmod n + 1, \left(y_i+vs_{i-1}-1\right)\bmod n + 1\right\} $$
$$ r_i=\max\left\{\left(x_i+vs_{i-1}-1\right)\bmod n + 1, \left(y_i+vs_{i-1}-1\right)\bmod n + 1\right\} $$
第 $i$ 个询问表示求 $\left\{a_{l_i},a_{ {l_i}+1},\dots,a_{r_i}\right\}$ 的最长上升序列长度。
输出格式
输出一行一个整数，表示 $\sum_{i=1}^{q}{i s_i} \bmod 1000000007$。
样例数据
样例 1 输入
5 3 0
1 3 2 1 4
1 2 3 2 3 4 3 5样例 1 输出
13样例 1 解释
| $i$ | $l_i$ | $r_i$ | 最长上升子序列 | $s_i$ |
|---|---|---|---|---|
| $1$ | $1$ | $5$ | $\{1,3,4\}$ | $3$ |
| $2$ | $4$ | $\{1,3\}$ | $2$ | |
| $3$ | $4$ | $5$ | $\{1,4\}$ |
其中“最长上升子序列”可能不唯一。
样例 2 输入
5 3 1
1 3 2 1 4
1 2 3 2 3 4 3 5样例 2 输出
14样例 2 解释
| $i$ | $l_i$ | $r_i$ | 最长上升子序列 | $s_i$ |
|---|---|---|---|---|
| $1$ | $1$ | $5$ | $\{1,3,4\}$ | $3$ |
| $2$ | $2$ | $4$ | $\{2\}$ | $1$ |
| $3$ | $1$ | $5$ | $\{1,2,4\}$ | $3$ |
其中“最长上升子序列”可能不唯一。
样例 3
见下载目录下的 ex_3.in 与 ex_3.ans。
样例 4
见下载目录下的 ex_4.in 与 ex_4.ans。
子任务
各组测试数据满足下列限制条件：
| 测试点编号 | $n=$ | $q=$ |
|---|---|---|
| 1,2 | $10^{2}$ | $3 \times 10^{4}$ |
| 3,4 | $3 \times 10^{3}$ | |
| 5,6 | $5 \times 10^{4}$ | |
| 7,8 | $3 \times 10^{3}$ | $10^{6}$ |
| 9,10 | $5 \times 10^{4}$ | |
| 11,12 | $3 \times 10^{6}$ | |
| 13,14 | $5 \times 10^{6}$ | |
| 15,16 | $10^{5}$ | |
| 17,18 | $5 \times 10^{4}$ | $10^{7}$ |
| 19,20 | $10^{5}$ |
此外，对于编号为奇数的测试点，满足 $v=0$；对于编号为偶数的测试点，满足 $v=1$。
在提交代码后将为你评测预测试数据并返回结果。本题的预测试数据包含 $20$ 个测试点，每个测试点的数据规模限制与对应编号的最终测试点相同。
注意：预测试数据的评测结果与最终评测结果没有关系。
提示
注意时间限制。