你有一个数组 $$$a$$$ 最初是空的。您必须在阵列上处理以下类型的 $$$q$$$ 查询。
- 类型 1:删除$$$a$$$的中间元素。形式上,如果 $$$a$$$ 具有 $$$n$$$ 元素,则删除 $$$a$$$ 的 $$$\lceil \frac{n}{2} \rceil$$$-th$$$^{\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$$$,i。 e.大于或等于 $$$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$$$ 的长度不会是 $$$10^9 + 7$$$ 的倍数。
还保证每个测试用例至少包含一个第三类查询,并且所有测试用例$$$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 \lt M$$$ 和 $$$x \cdot Q \equiv P \pmod{M}$$$ 。
示例
输入复制
252 12 2313102 3353212 9385562 5595032 35311531313
输出复制
8333333557856804480553793656724179701
注意
在第一个测试用例中,数组 $$$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]$$$。