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