D. Dark Alley
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

One cold and foggy night, you walk down a shady alley. There should be a lamp every few metres but none of them seem to work, and in this night, not even the moon enlightens your path. Alone and in the dark, you wonder: "Even if there was a working lamp somewhere, how much would it lighten my way?". Now, back at home, you want to calculate this.

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\cdot10^5, 0 \lt p \lt 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:
      [noitemsep,topsep=0pt,parsep=0pt,partopsep=0pt]
    • "+ b x" 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$$$.
    • "- b x" 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.
    • "? x" 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.

Examples
Input
5 6 0.25
+ 4 2
? 1
? 2
? 3
? 4
? 5
Output
3
4
3
250000004
187500003
Input
5 7 0.33
+ 9 1
? 5
+ 4 3
? 2
? 5
- 9 1
? 2
Output
312342734
470000012
341542736
760000008
Note

The brightness in the alley after placing the lamp will look like this:

3432.251.6875