题目描述

这条小巷可以被建模为一条长度为 $n$ 米的直线。 雾的密度是均匀的，每经过 $1$ 米，雾会使灯光衰减 $1-p$ 倍。 某一点的亮度等于所有灯光到达该点的光强之和。 你需要在放置一些灯之后，计算某些点的亮度。

输入格式

输入包括：

• 一行，包含两个整数 $n$ 和 $q$，以及一个实数 $p$（$1\leq n, q\leq 2\cdot10^5, 0 < p < 1$），分别表示小巷的长度、查询次数和雾的密度。雾的密度 $p$ 最多有 $6$ 位小数。

• 接下来 $q$ 行，每行包含以下三种查询之一：

  1. “$\texttt{+ b x}$” 给定两个整数 $b$ 和 $x$（$1\leq b \leq 10^9$ 且 $1\leq x \leq n$），表示在位置 $x$ 放置一个亮度为 $b$ 的灯。
  2. “$\texttt{- b x}$” 给定两个整数 $b$ 和 $x$（$1\leq b \leq 10^9$ 且 $1\leq x \leq n$），表示移除在位置 $x$ 上亮度为 $b$ 的灯。保证之前在该位置放置过该亮度的灯。
  3. “$\texttt{? x}$” 给定一个整数 $x$（$1\leq x \leq n$），询问位置 $x$ 的亮度。

输出格式

可以证明，亮度可以表示为一个分数 $\frac{P}{Q}$，其中 $Q$ 不会被 $10^9+7$ 整除。对于每个“$\texttt{?}$”类型的查询，输出 $P\cdot Q^{-1} \bmod 10^9+7$，每个答案占一行。

输入输出样例 #1

输入 #1

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

输出 #1

3
4
3
250000004
187500003

输入输出样例 #2

输入 #2

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

输出 #2

312342734
470000012
341542736
760000008

说明/提示

在第一个样例中，放置灯后小巷各点的亮度如下表所示：