在一个寒冷多雾的夜晚，你走在一条阴暗的小巷里。巷子里本应每隔几米就有一盏路灯，但似乎没有一盏是亮的，今晚连月光也无法照亮你的路。独自走在黑暗中，你心想：“即使某处有一盏亮着的灯，它又能照亮我多少路呢？”现在，回到家后，你想计算一下这个问题。

这条小巷可以建模为一条长度为 $n$ 米的线段。雾的密度是均匀的，每米会将灯光的亮度降低 $1 - p$ 倍。某一点的亮度是所有灯光到达该点的亮度之和。你需要在放置一些灯后，计算某些位置的亮度。

输入格式

输入包含： 第一行包含两个整数 $n$ 和 $q$ 以及一个实数 $p$ ($1 \le n, q \le 2 \cdot 10^5, 0 < p < 1$)，分别表示小巷的长度、查询次数和雾的密度。雾的密度 $p$ 最多给出小数点后 6 位。 $q$ 行，每行包含以下三种查询类型之一： “+ b x”：给定两个整数 $b$ 和 $x$ ($1 \le b \le 10^9$ 且 $1 \le x \le n$)，在位置 $x$ 放置一盏亮度为 $b$ 的灯。 “- b x”：给定整数 $b$ 和 $x$ ($1 \le b \le 10^9$ 且 $1 \le x \le n$)，移除位置 $x$ 处亮度为 $b$ 的灯。保证该位置之前放置过亮度为 $b$ 的灯。 * “? x”：给定一个整数 $x$ ($1 \le x \le n$)，计算位置 $x$ 的亮度。

输出格式

可以证明亮度可以表示为一个分数 $\frac{P}{Q}$，其中 $Q$ 不能被 $10^9 + 7$ 整除。对于每个“?”查询，请以 $P \cdot Q^{-1} \pmod{10^9 + 7}$ 的形式输出亮度，每行输出一个结果。

雾中的小巷。摄影：Henryk Niestrój

样例

输入 1

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

输出 1

3
4
3
250000004
187500003

说明 1

放置灯后，小巷中的亮度如下： 3 4 3 2.25 1.6875

输入 2

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

输出 2

312342734
470000012
341542736
760000008