SOLVE

LATER

Mancunian And Multiplicative Queries

/

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.

- \(1 \le N, Q \le 50,000\)
- \(1 \le C \le 1,000,000\)
- \(1 \le L \le R \le N\)

Explanation

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*.

Time Limit:
5.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...