G. Баланс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$, который изначально пуст. Вам нужно обработать $$$q$$$ запросов следующих типов на вашем массиве.

  • Тип 1: Удалите средний элемент массива $$$a$$$. Формально, если в массиве $$$a$$$ сейчас $$$n$$$ элементов, удалите $$$\lceil \frac{n}{2} \rceil$$$-й$$$^{\text{∗}}$$$ элемент массива $$$a$$$ и объедините оставшиеся части. Гарантируется, что массив $$$a$$$ не пустой, когда вам поступает запрос этого типа.
  • Тип 2: Вставьте $$$x$$$ в начало, конец и между каждыми двумя последовательными элементами массива $$$a$$$. Формально, если $$$a = [a_1, a_2, \ldots, a_n]$$$ до этого запроса, то после запроса массив $$$a$$$ станет $$$[x, a_1, x, a_2, x, \ldots, x, a_n, x]$$$.
  • Тип 3: Выведите сумму балансов всех $$$2^L - 1$$$ непустых подпоследовательностей$$$^{\text{†}}$$$ массива $$$a$$$, где $$$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$$$ не будет кратной $$$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}$$$.

Пример
Входные данные
2
5
2 1
2 2
3
1
3
10
2 33532
1
2 938556
2 559503
2 353115
3
1
3
1
3
Выходные данные
833333355
7
856804480
553793656
724179701
Примечание

В первом наборе входных данных массив $$$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]$$$.