Description

在一个寒冷而有雾的夜晚，你走在一条阴暗的小巷里。 每隔几米应该有一盏路灯，但似乎没有一盏能亮起，在这个夜晚，连月亮都无法照亮你的路。 孤身一人在黑暗中，你不禁思考： “即使某处有一盏亮着的灯，它能照亮我多少路呢？” 现在，回到家中，你想要计算这个问题。

:::align{center} 雾蒙蒙的小巷。照片来自 Henryk Niestrój :::

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

Input Format

输入包括：

• 一行，包含两个整数 $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$ 的亮度。

Output Format

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

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

Hint

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

由 ChatGPT 4.1 翻译