Clark has a sequence of length $n$, denoted by $\left\{a_1, a_2, \dots, a_n\right\}$. Clark performs $q$ queries on this sequence. For each query, he selects a substring of the sequence and wants to know the length of its longest increasing subsequence.

A substring is a sequence formed by a contiguous part of the original sequence. We use parameters $l$ and $r$ to denote the substring $\left\{a_l, a_{l+1}, \dots, a_r\right\}$.

A subsequence is a new sequence obtained by deleting zero or more elements from the original sequence without changing the relative order of the remaining elements. For example, $\left\{a_3, a_4, a_6, a_8\right\}$ is a subsequence of $\left\{a_2, a_3, a_4, a_5, a_6, a_7, a_8\right\}$.

An increasing sequence is a sequence where every element is strictly greater than the previous one, except for the first element. For example, $\left\{2, 3, 5, 8\right\}$ is an increasing sequence, while $\left\{2, 3, 5, 5\right\}$ is not.

The length of a sequence is the number of elements it contains.

The longest increasing subsequence is the longest sequence among all possible increasing subsequences of a given sequence.

Input

The first line contains three non-negative integers $n, q, v$, representing the length of the sequence, the number of queries, and whether the queries are forced to be online, respectively. $v \in \{0, 1\}$, where $0$ means offline and $1$ means online.

The next line contains $n$ positive integers representing the sequence $\left\{a_1, a_2, \dots, a_n\right\}$. For $1 \le i \le n$, it is guaranteed that $1 \le a_i \le 1000$.

The next line contains $8$ integers $A, B, C, D, E, F, x_0, y_0$, representing parameters for generating the queries. It is guaranteed that $1 \le A, B, C, D, E, F, x_0, y_0 \le n$.

For $1 \le i \le q$, the substring for each query is given as follows: let $s_i$ be the answer to the $i$-th query (the length of the longest increasing subsequence), and let $s_0 = 0$. Then:

$$ 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\} $$

The $i$-th query asks for the length of the longest increasing subsequence of $\left\{a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\right\}$.

Output

Output a single integer representing $\sum_{i=1}^{q}{i s_i} \bmod 1000000007$.

Examples

Input 1

5 3 0
1 3 2 1 4
1 2 3 2 3 4 3 5

Output 1

13

Note

For $i=1$, the substring is $\{1, 3, 2, 1, 4\}$, the longest increasing subsequence is $\{1, 3, 4\}$, so $s_1=3$. For $i=2$, the substring is $\{1, 3, 2, 1\}$, the longest increasing subsequence is $\{1, 3\}$, so $s_2=2$. For $i=3$, the substring is $\{1, 4\}$, the longest increasing subsequence is $\{1, 4\}$, so $s_3=2$. The "longest increasing subsequence" may not be unique.

Input 2

5 3 1
1 3 2 1 4
1 2 3 2 3 4 3 5

Output 2

14

Note

For $i=1$, the substring is $\{1, 3, 2, 1, 4\}$, the longest increasing subsequence is $\{1, 3, 4\}$, so $s_1=3$. For $i=2$, the substring is $\{3, 2, 1\}$, the longest increasing subsequence is $\{3\}$ or $\{2\}$ or $\{1\}$, so $s_2=1$. For $i=3$, the substring is $\{1, 3, 2, 1, 4\}$, the longest increasing subsequence is $\{1, 2, 4\}$, so $s_3=3$. The "longest increasing subsequence" may not be unique.

Input 3

See ex_3.in and ex_3.ans in the download directory.

Input 4

See ex_4.in and ex_4.ans in the download directory.

Subtasks

Each test case satisfies the following constraints:

Additionally, for test cases with odd IDs, $v=0$; for test cases with even IDs, $v=1$.

After submitting your code, the pretest data will be evaluated and the results returned. This problem's pretest data contains $20$ test cases, each with the same data scale constraints as the corresponding final test case.

Note: The evaluation results of the pretest data have no relation to the final evaluation results.

提示

注意时间限制。