Mancunian And Multiplicative Queries
Tag(s):

## Medium, Sqrt-Decomposition

Problem
Editorial
Analytics

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 $$\prod_{i=1}^{C} FUNC[cnt_i]$$ 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$
SAMPLE INPUT
5 5 3
1 2 2 3 3
1 1 2 3 4 5
2 4
1 2
4 5
SAMPLE OUTPUT
4
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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

August Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Data Structures > Trees
• Algorithms > Graphs
• Algorithms > Graphs
• Algorithms > String Algorithms