ADDGP - Enjoy Adding GP to Series

You are initially given an empty array of Size N (<=100000). (i.e. each element is 0).

Given 2 <= R <=109.

Now you are given 3 types of query:

  • "0 St i1 i2": means add (St, St*R, St*R^2, ...) GP from i1 to i2 respectively. (Means add the GP with start term St and common ratio R in the series beginning from i1 and ending at i2.)
  • "1 i j": means find the sum of values of the array from index i to index j with modulo 1000000007.
  • "2 i": resets the i-th index array to 0.

Constraints

Queries <=90000
1 <= St <= 109

Input

First Line contains N R Q.
Then Follows Q lines, each line can be of any 3 types described above.

Output

Output only second type of Query.

Example

Input:
2 2 3
0 2 1 2
1 1 2
1 2 2

Output:
6
4

Click here to see my set of problems at Spoj.


Added by:devu
Date:2013-08-30
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2016-05-19 10:53:47
Getting WA on testcase 10. Plz Help.
Edit: Finally AC. Beware of stupid typos.

Last edit: 2016-05-25 15:53:42
2015-12-21 10:33:34 ashish kumar
After So many many silly mistakes finally AC , feeling relaxed :)
2015-12-21 09:00:18 ashish kumar
My solution is giving WA on 10th testcase.
2015-12-10 04:48:38 Akashdeep Goel
Kindly tell where my code is Wrong ...I have figured correct logic and debugged all silly mistakes..Spent so much time on this :-(

Last edit: 2015-12-10 04:48:50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.