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:

• "0 St i1 i2": means add (St, St×R, St×R², ...) 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 ≤ 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.