On friendship day , Thundercracker gifted Tihor an array A of N positive integers instead of chocolates. In order to get the chocolates, Tihor has to solve the following problem given by Thundercracker efficiently:

Thundercracker asks Tihor Q queries. In each query, you are given two integers L and R. You have to compute and print the value of below expression:

$(\prod_{P}\prod_{P^d | (A[L]..A[R])} \phi(P) ) \% (10^9 + 7)$

• P must be prime.
• $(A[L]..A[R])$ denotes a subarray of A consisting of elements $A[L], \ A[L + 1], \ ..., \ A[R]$.
• $P^d$ ($d \gt 0$) divides subarray $(A[L]..A[R])$ if it divides atleast one element in that subarray.
• $\phi()$ is the Euler's totient function.

Tihor is worried and find this problem very difficult. Will you help him?

Input format

The first line contains N and Q, number of elements in an array A and number of queries respectively.
Second line contains N space separated integers, $i_{th}$ of them denotes $A[i]$.
Third line contains four space separated integers $\alpha$, $\beta$, $\gamma$, $\delta$.

Query generation

You need to generate Q queries in the following way.
Let $Ans_i$ denote the answer for $i_{th}$ query and $Ans_0 = 0$. Then for $i_{th} (i \geq 1)$ query,

$L_i$ = $1 + (\alpha * Ans_{i - 1} + i * \beta) \% N$.
$R_i$ = $L_i + (\gamma * Ans_{i - 1} + i * \delta) \% (N - L_i + 1)$.

Output format

For each query, print the required answer in a singe line.

Constraints

$1 \leq N \leq 10^5$
$1 \leq Q \leq 10^6$
$1 \leq A[i] \leq 10^5$
$0 \leq \alpha, \beta, \gamma, \delta \leq 10^9$