All submissions for this problem are available.
Are you fond of playing games? Well most people are, especially the children love to play games on their computer. And David is one of them.He is very fond of this game called “Bubble Burst” on his computer. He has literally got addicted to it. So the game is that random bubbles appear on the screen, each of them carrying a distinct number on them. This game is particularly made to improve the calculations of children like David. The rule is that you score as many points as the number on the bubble you burst, but first you need to generate that number by multiplying a contiguous sequence of numbers. For example, you are given the numbers 1 2 3 4 5, then you can generate 12 by multiplying 3 and 4, or 120 by multiplying all the numbers. You can multiply any contiguous sequence of numbers, but you cannot multiply random numbers. For example, you cannot multiply 2 and 5 in the sequence mentioned above. Now David has played this game a lot and it has really made him very fast with calculations. But as the game progresses, the levels become harder and the numbers become bigger along with the increase in the number of bubbles. Also, you are given a sequence of numbers in the beginning so that you can generate numbers by multiplication. This sequence is also updated in between so as to allow the generation of new numbers.
As said already, David likes this game a lot and it has really helped him improve his calculation speed. He has played it umpteen times but this time he wishes to set a new benchmark by making a high score which sets the bar very high. Since the numbers get bigger and the levels become harder every minute, he asks for your help to deal with such large numbers and make a new record score. He wishes that you make a program where he can give you two numbers L and R specifying the beginning and the end of the segment whose product he wants, or the location L where he wishes to update the value with R.
The first line of the input consists of N denoting the no of numbers in the sequence. The next line contains N space separated integers which describe the sequence. The next line contains Q denoting the numbers of queries. Then Q lines follow which describe the query. There can be two types of query. Each query starts with a string followed by two numbers, L and R. The string can be either “MUL”, asking you to find out the product of the sequence in the range L to R (both inclusive), or “MOD” which means that you need to modify the L-th value in the string with the number R.
Output on a new line the result of each query starting with “MUL”. Since the value of this result can be very large, display the result modulo 1000000007 (10^9+7).
1<=Value in the sequence<=10^18
1<=L<=R<=N for a “MUL” query
1<=L<=N and 1<=R<=10^18 for a “MOD” query
1 2 3 4 5
MUL 2 5
MOD 1 5
MUL 1 3
Problem Setter: Ayush Jaggi, 2nd Year
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.