CF2180G.Balance

You have an array $a$ which is initially empty. You have to process $q$ queries of the following types on your array.

• Type 1: Erase the middle element of $a$. Formally, if $a$ has $n$ elements, remove the $\lceil \frac{n}{2} \rceil$-th$^{\text{∗}}$ element of $a$ and concatenate the remaining parts. It's guaranteed that $a$ is non-empty whenever you are given a query of this type.
• Type 2: Insert $x$ at the beginning, the end, and between every two consecutive elements of $a$. Formally, if $a = [a_1, a_2, \ldots, a_n]$ before this query, $a$ will become $[x, a_1, x, a_2, x, \ldots, x, a_n, x]$ after the query.
• Type 3: Output the sum of the balances of all $2^L - 1$ non-empty subsequences$^{\text{†}}$ of $a$, where $L$ is the length of $a$ at this moment. It is guaranteed that $L$ will not be a multiple of $10^9 + 7$ whenever this query is processed.

The balance of an array $b = [b_1, b_2, \ldots, b_m]$ is defined as $$ \text{balance}(b) = \frac{1 \cdot b_1 + 2 \cdot b_2 + \ldots + m \cdot b_m}{m}. $$

$^{\text{∗}}$$\lceil k \rceil$ is the $k$ rounded up, i. e. the smallest integer greater than or equal to $k$.

$^{\text{†}}$A sequence $b$ is a subsequence of a sequence $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) element from arbitrary positions. Two subsequences are considered different if the sets of positions of the deleted elements are different.

你有一个初始为空的数组 $a$。你需要对这个数组执行 $q$ 个查询，查询类型如下：

• 类型 1：删除 $a$ 的中间元素。形式化地，若 $a$ 当前有 $n$ 个元素，则删除其第 $\lceil \frac{n}{2} \rceil$ 个$^{\text{∗}}$元素，并将剩余两部分拼接起来。保证每次给出此类查询时，$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$ 个非空子序列$^{\text{†}}$ 的“平衡值”之和，其中 $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$ 的一个子序列。若两个子序列所删除元素的位置集合不同，则认为它们是不同的子序列。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $q$ ($2 \leq q \leq 10^6$), denoting the number of queries. The next $q$ lines describe the queries:

• Each query of type 1 is in the form 1, which means to erase the middle element of $a$. It's guaranteed that $a$ is non-empty whenever you are given a query of this type.
• Each query of type 2 is in the form 2 x, where $x$ is an integer to be inserted as described and $1 \le x \le 10^9$.
• Each query of type 3 is in the form 3, which means to output the sum of the balances of all non-empty subsequences of $a$. It is guaranteed that the length of $a$ will not be a multiple of $10^9 + 7$ whenever this query is processed.

It is also guaranteed that each test case contains at least one query of the third type, and that the total sum of $q$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 的长度不为 $10^9 + 7$ 的倍数。

此外，保证每个测试用例中至少包含一个类型 3 的查询，且所有测试用例的 $q$ 总和不超过 $10^6$。

For each query of type 3, output the desired sum of balances.

Formally, let $M = 10^9+7$. It can be shown that the exact answer can be expressed as an irreducible fraction $\frac{P}{Q}$, where $P$ and $Q$ are integers and $Q \not \equiv 0 \pmod{M}$. Output the integer equal to $P \cdot Q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot Q \equiv P \pmod{M}$.

对于每个类型为 3 的查询，输出所要求的余额总和。

形式化地，令 $M = 10^9+7$。可以证明，精确答案可表示为既约分数 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 为整数，且 $Q \not \equiv 0 \pmod{M}$。请输出整数 $P \cdot Q^{-1} \bmod M$。换言之，请输出满足 $0 \le x \lt M$ 且 $x \cdot Q \equiv P \pmod{M}$ 的整数 $x$。

In the first test case, the array $a$ is initially empty.

After the first query, the array becomes $[1]$.

After the second query, the array becomes $[2,\, 1,\, 2]$.

In the third query, the subsequences of $a$ and their balances are as follows:

• Subsequence $[1]$ with balance $$\frac{1 \cdot 1}{1} = 1;$$
• Two subsequences $[2]$, each having balance $$\frac{1 \cdot 2}{1} = 2;$$
• Subsequence $[1,\,2]$ with balance $$\frac{1 \cdot 1 + 2 \cdot 2}{2} = \frac{5}{2};$$
• Subsequence $[2,\,1]$ with balance $$\frac{1 \cdot 2 + 2 \cdot 1}{2} = 2;$$
• Subsequence $[2,\,2]$ with balance $$\frac{1 \cdot 2 + 2 \cdot 2}{2} = 3;$$
• Subsequence $[2,\,1,\,2]$ with balance $$\frac{1 \cdot 2 + 2 \cdot 1 + 3 \cdot 2}{3} = \frac{10}{3}.$$

Thus, the total sum of balances is: $$\frac{95}{6}.$$

After the fourth query, the array $a$ becomes $[2,\,2]$.

在第一个测试用例中，数组 $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]$。