SOLVE
LATER
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$$.