Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is experimenting in his kitchen. He has $N$ spices (numbered $0$ through $N-1$) with types $S_{0}, S_{1}, \ldots, S_{N-1}$.

You should answer $Q$ queries. Each query is described by two integers $L$ and $R$. In each query, Chef wants to use the spices $S_{L}, S_{L+1}, \ldots, S_{R}$ in some order to make a dish. However, he has no clue about the order in which he should use them to make a perfect dish, so he wants to try all possible orders (sequences created by permuting these $R-L+1$ spices) to find out. Tell Chef the number of distinct orders (sequences) of spices he needs to try. Since this number can be very large, compute it modulo $10^{9}+7$.

Two sequences of spices are considered different if there is a valid index $i$ such that the type of the $i$-th spice in one sequence is different from the type of the $i$-th spice used in the other sequence.

Note that the input is encoded so that you have to answer the queries online.

------ Input ------
The first line of the input contains two space-separated integers $N$ and $Q$.
The next line contains $N$ space-separated integers $S_{0}, S_{1}, S_{2}, \ldots, S_{N-1}$.
Each of the next $Q$ lines contains four space-separated integers $L_{1}$, $L_{2}$, $R_{1}$ and $R_{2}$ describing a query. The parameters $L$ and $R$ can be calculated in the following way:
- Let's denote the answer to the previous query by $a$; for the first query, $a = 0$.
- Calculate $L = (L_{1} \cdot a + L_{2}) \% N$ and $R = (R_{1} \cdot a + R_{2}) \% N$.
- Then, if $L > R$, swap $L$ and $R$.

------ Output ------
For each query, print a single line containing one integer — the number of distinct orders of spices modulo $10^{9}+7$.

------ Constraints ------
$1 ≤ N, Q ≤ 3 \cdot 10^{5}$
$1 ≤ S_{i} ≤ 10^{9}$ for each valid $i$
$0 ≤ L_{1}, L_{2}, R_{1}, R_{2} ≤ N-1$

------ Subtasks ------
Subtask #1 (10 points): $1 ≤ N, Q ≤ 10^{3}$

Subtask #2 (40 points):
$1 ≤ N, Q ≤ 10^{5}$
$L_{1} = R_{1} = 0$

Subtask #3 (30 points): $1 ≤ N, Q ≤ 10^{5}$

Subtask #4 (20 points): original constraints

----- Sample Input 1 ------
5 3

1 2 3 7 10

1 1 1 1

2 1 3 4

0 0 0 4
----- Sample Output 1 ------
1

2

120

见题面

见题面