G. Balance
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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

Example
Input
2
5
2 1
2 2
3
1
3
10
2 33532
1
2 938556
2 559503
2 353115
3
1
3
1
3
Output
833333355
7
856804480
553793656
724179701
Note

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]$$$.