A16800 | Balance

你有一个最初为空的数组 $a$。你需要对该数组处理 $q$ 个如下类型的操作：

- 操作 1：删除 $a$ 的中间元素。具体来说，假设 $a$ 有 $n$ 个元素，移除第 $\lceil \frac{n}{2} \rceil$ 个元素，并将剩余部分拼接。保证在给出此操作时 $a$ 非空。
- 操作 2：在 $a$ 的首、尾以及每两个相邻元素之间插入 $x$。具体来说，如果操作前 $a = [a_1, a_2, \ldots, a_n]$，那么操作后 $a = [x, a_1, x, a_2, x, \ldots, x, a_n, x]$。
- 操作 3：输出 $a$ 当前所有 $2^L - 1$ 个非空子序列的平衡值之和，其中 $L$ 表示 $a$ 当前的长度。保证每次处理此操作时 $L$ 不会为 $10^9+7$ 的倍数。

数组 $b = [b_1, b_2, \ldots, b_m]$ 的平衡值定义为
$$ \text{balance}(b) = \frac{1 \cdot b_1 + 2 \cdot b_2 + \ldots + m \cdot b_m}{m}. $$

$^{\text{∗}}$ $\lceil k \rceil$ 表示 $k$ 向上取整，即不小于 $k$ 的最小整数。

$^{\text{†}}$ 如果 $b$ 可以通过从 $a$ 的任意位置删除若干（可以为零或全部）元素得到，则 $b$ 是 $a$ 的一个子序列。若删除元素的下标集合不同，则两个子序列被视为不同。

每个测试点包含多组测试数据。首行为测试数据组数 $t$（$1 \le t \le 10^4$）。接下来是各组测试数据的描述。

每组测试数据的第一行为一个整数 $q$（$2 \leq q \leq 10^6$），表示操作数。随后 $q$ 行，每行描述一个操作：

- 类型 1 的操作形如 1，即删除 $a$ 的中间元素。保证此时 $a$ 非空。
- 类型 2 操作为 2 x，其中 $x$ 是要插入的整数，$1 \le x \le 10^9$。
- 类型 3 操作为 3，即输出 $a$ 的所有非空子序列的平衡值之和。保证此时 $a$ 的长度 $L$ 不会是 $10^9+7$ 的倍数。

另保证每组测试数据至少包含一个类型 3 请求，所有测试数据中 $q$ 的总和不超过 $10^6$。

对每个类型 3 的查询，输出所求平衡值之和。

具体来说，设 $M = 10^9+7$。可以证明，最终答案可表示为最简分数 $\frac{P}{Q}$，其中 $P,Q$ 为整数，且 $Q \not\equiv 0 \pmod{M}$。你需要输出 $P \cdot Q^{-1} \bmod M$，即输出一个 $x$，满足 $0 \le x < M$ 且 $x \cdot Q \equiv P \pmod{M}$。