Mancunian is in a hurry! He is late for his date with Nancy. So he has no time to deal with a long and complex problem statement.
You are given two arrays, A and $FUNC$. Each element of either array, $A_i$ or $FUNC_i$, is a positive integer not greater than C. Given Q queries, each of the form L R, the answer for each query is $$\begin{equation} \prod_{i=1}^{C} FUNC[cnt_i] \end{equation}$$ where $cnt_i$ is the frequency of the integer i in the range L R.
The answer to the problem is the product of the answers of all the individual queries modulo $10^9+7$.

Input format

The first line contains three integers N, C and Q denoting the size of the array, the range of allowed values for each array element and the number of queries respectively.
The second line contains N positive integers, denoting the elements of the array A. The $ith$ (1-indexed) of these represents $A_i$.
The third line contains $N+1$ positive integers, denoting the elements of the array $FUNC$. The $ith$ (0-indexed) of these represents $FUNC_i$.
The $ith$ of the next Q lines contains two integers, L and R for the $ith$ query.

Output format

Print a single integer, which is the answer to the given problem.

Constraints

• $1 \le N, Q \le 50,000$
• $1 \le C \le 1,000,000$
• $1 \le L \le R \le N$