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\).
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.
Print a single integer, which is the answer to the given problem.
In the range specified by the first query, there are 0 occurrences of 1, 2 occurrences of 2, 1 occurrence of 3 and 0 occurrences of both 4 and 5. So the answer for the first query is \(FUNC[0]\) * \(FUNC[2]\) * \(FUNC[1]\) * \(FUNC[0]\) * \(FUNC[0]\) \(=\) 2.
In the range specified by the second query, there is 1 occurrence of 1, 1 occurrence of 2, 0 occurrences of 3 and 0 occurrences of both 4 and 5. So the answer for the second query is \(FUNC[1]\) * \(FUNC[1]\) * \(FUNC[0]\) * \(FUNC[0]\) * \(FUNC[0]\) \(=\) 1.
In the range specified by the third query, there are 0 occurrences of 1, 0 occurrences of 2, 2 occurrences of 3 and 0 occurrences of both 4 and 5. So the answer for the third query is \(FUNC[0]\) * \(FUNC[0]\) * \(FUNC[2]\) * \(FUNC[0]\) * \(FUNC[0]\) \(=\) 2.
Hence the final answer is 2 * 1 * 2 \(=\) 4.