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\)

Subtask	Points
\(\alpha = \gamma = 0\)	\(20\%\)
\(1 \leq N, Q, A[i] \leq 10^3\)	\(20\%\)
Original Constraints	\(60\%\)