Shil and Magic of Arrays
Shil has an array of N elements A_{1} , A_{2} .... A_{N} . He wants to perform two types of operations on this array.
- 1 i K: Update the value of A_{i} to K i.e do A_{i} = K
- 2 P : Find the magical value of subarray A_{1}, A_{2} .... A_{P}
The magical value of array
B_{1} ,
B_{2} ....
B_{r} is defined as product of
(f[i]+1)^{(f[i]+1)} where
f[i] is the number of times
i occurs in array
B.
Input:
First line of input contains N and Q denoting length of array A and number of operations to be performed respectively.
Next Q lines consists of operations of type 1 or type 2 in the format mentioned above. Each element of array is initially initialized to 0.
Output:
For each operation of type 2 , output the magical value modulo 10^{9} + 7.
Constraints:
- 1 ≤ N ≤ 2 * 10^{5}
- 1 ≤ Q ≤ 2 * 10^{5}
- 1 ≤ P, K ≤ N
Explanation
In first query , we update A_{3} to 6.
Answer for second query will be ( f[0]+1)^{(f[0]+1)} , thats 3^{3}
Answer for third query will be ( f[0]+1)^{(f[0]+1)} * ( f[6]+1)^{(f[6]+1)} , thats 8^{8} * 2^{2}
Time Limit:
4.0 sec(s)
for each input file.
Memory Limit:
512 MB
Source Limit:
1024 KB
Marking Scheme:
Marks are awarded when all the testcases pass.
Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic