Collecting Magical Berries

All submissions for this problem are available.
ChefLand is very famous for its magical forests. There you can find a lot of different trees, fruits, mushrooms and many other charming things. Recently, N bushes of magical berries (numbered 1 to N) have been discovered. The berries are in fact very tasty, and it has become very popular among the tourists to pick these berries (don't worry, as the berries are magical, they'll grow next night again :) ).
Groups of tourists often want to go for a walk to pick some berries. For the ith group it is known that it consists of K_{i} people and they will collect all the berries, from K_{i} consecutive bushes, beginning from the L_{i}th, going to the L_{i+1}th, the L_{i+2}th and so on. Generally, a plan of the ith group of tourists can be described by the numbers L_{i} and R_{i}  the leftmost and the rightmost bush for the ith group. When the group have picked some amount of berries, we consider that they've picked all the berries from the bushes from the L_{i}th to the R_{i}th, they want to divide them fairly. Fair division is a division in such a way, that the difference between the maximal and the minimal number of berries a single tourist from the group receives is less than two. All the berries (even from a single bush) are different. Generally, there are a lot of ways to divide them fairly. For example, you can divide fairly two berries between two tourists in two ways.
Some tourists are fond of dividing the berries. So, they will get upset if the number of ways to divide them is too small. But some tourists will get upset if the number of ways if too huge, they will find it quite confusing. So, the ChefLand tourist agency has offered the following service: for each group of tourists they tell the number of ways to divide the berries
fairly among them after the walk. As they currently don't have enough employees, they've asked you to help them. Of course, the number of berries on bushes changes during a day. You'll receive this information. Also, you'll receive the information about the groups of tourists. For each group of tourists, please tell the number of ways to divide collected berries fairly. We understand that this number can be quite huge, so we ask you to calculate it modulo 3046201.
Input
The first line of the input consists of a single integer N  the number of bushes.
The second line consists of N integers  the ith integer corresponds to the amount of the berries on the ith bush in the beginning.
The third line consists of a single integer Q  the number of requests given to your program.
Next Q lines are the lines of the following form: "change A B"  then the amount of the berries on the bush A becomes equal to B, or "query L R"  if a group of tourists wants to visit all the bushes from the Lth to the Rth, what is the number of ways to divide their collected berries fairly, modulo 3046201.
Output
For each "query L R" request, output the number of ways, asked in the statement, modulo 3046201. Output one number on a single line.
Constraints
 1<=N<=100000
 1<=Q<=100000
 You can assume that the number of berries on a single bush will not exceed 30
Example
Input: 8 2 1 1 2 1 2 2 2 5 change 2 2 query 1 8 query 5 7 query 3 3 query 4 4 Output: 2065880 90 1 1
Author:  xcwgf666 
Tester:  tuananh93 
Editorial  http://discuss.codechef.com/problems/COLLECT 
Tags  combinatorics, june13, medium, xcwgf666 
Date Added:  30112012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions