CFCF2180G.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}$。

在第一个测试用例中，初始时数组 $a$ 为空。

第一次操作结束后，数组为 $[1]$。

第二次操作后，数组为 $[2,\, 1,\, 2]$。

第三次操作时，$a$ 的子序列及其平衡值如下：

• 子序列 $[1]$ 的平衡值为

  $$\frac{1 \cdot 1}{1} = 1;$$

• 两个 $[2]$ 子序列，各自平衡值

  $$\frac{1 \cdot 2}{1} = 2;$$

• 子序列 $[1,\,2]$ 的平衡值

  $$\frac{1 \cdot 1 + 2 \cdot 2}{2} = \frac{5}{2};$$

• 子序列 $[2,\,1]$ 的平衡值

  $$\frac{1 \cdot 2 + 2 \cdot 1}{2} = 2;$$

• 子序列 $[2,\,2]$ 的平衡值

  $$\frac{1 \cdot 2 + 2 \cdot 2}{2} = 3;$$

• 子序列 $[2,\,1,\,2]$ 的平衡值

  $$\frac{1 \cdot 2 + 2 \cdot 1 + 3 \cdot 2}{3} = \frac{10}{3}.$$

因此，平衡值之和为

$$\frac{95}{6}.$$

第四次操作后，$a$ 变为 $[2,\,2]$。