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

Given 2 <= R <=10⁹.

Now you are given 3 types of query:

1. "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 begining from i1 and ending at i2.)
2. "1 i j": means find the sum of values of the array from index i to index j with modulo 1000000007.
3. "2 i": resets the i-th index array to 0.

Constraints

Queries <=90000
1 <= St <= 10⁹

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.