Problem D
Dark Alley

A foggy alley. Photo by Henryk Niestrój

The alley can be modelled as a line with a length of $n$ metres. The fog has a uniform density and reduces the light of a lamp by a factor of $1-p$ every metre. The brightness at one point is the sum of the light that reaches this point from every lamp. You want to calculate this brightness at some points after placing some lamps.

Input

The input consists of:

• One line with two integers $n$ and $q$ and one real number $p$ ($1\leq n, q\leq 2\cdot 10^5, 0 < p < 1$), the length of the alley, the number of queries and the density of the fog. The density $p$ of the fog will be given with at most $6$ digits behind the decimal point.

• $q$ lines containing one of three query types:

  1. given two integers $b$ and $x$ ($1\leq b \leq 10^9$ and $1\leq x \leq n$), place a lamp with brightness $b$ at position $x$.

  2. given integers $b$ and $x$ ($1\leq b \leq 10^9$ and $1\leq x \leq n$), remove a lamp with brightness $b$ at position $x$. It is guaranteed that a lamp with that brightness was placed there earlier.

  3. given one integer $x$ ($1\leq x \leq n$), calculate the brightness at position $x$.

Output

It can be shown that the brightness can be calculated as a fraction $\frac{P}{Q}$ where $Q$ is not divisible by $10^9+7$. For each query of type “?”, print the brightness as $P\cdot Q^{-1} \bmod 10^9+7$ in a single line.

Note

In the first sample the brightness in the alley after placing the lamp will look like this:

5 6 0.25
+ 4 2
? 1
? 2
? 3
? 4
? 5

3
4
3
250000004
187500003

5 7 0.33
+ 9 1
? 5
+ 4 3
? 2
? 5
- 9 1
? 2

312342734
470000012
341542736
760000008