D. Действительно, ещё одна задача о числах
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Three r there are's in strawberry.

Вам дан массив $$$b$$$ длины $$$m$$$. Вы можете выполнить следующую операцию любое количество раз (возможно, нулевое):

  • Выбрать два различных индекса $$$i$$$ и $$$j$$$, где $$$\bf{1\le i < j\le m}$$$ и $$$b_i$$$ является чётным числом, поделить $$$b_i$$$ на $$$2$$$ и умножить $$$b_j$$$ на $$$2$$$.

Ваша задача — максимизировать сумму массива после выполнения любого количества таких операций. Поскольку она может быть большой, выведите эту сумму по модулю $$$10^9+7$$$.

Поскольку эта задача слишком простая, вам дается массив $$$a$$$ длины $$$n$$$, и вам нужно решить задачу для каждого префикса $$$a$$$.

Другими словами, обозначив максимальную сумму $$$b$$$ после выполнения любого количества таких операций как $$$f(b)$$$, вам нужно вывести $$$f([a_1])$$$, $$$f([a_1,a_2])$$$, $$$\ldots$$$, $$$f([a_1,a_2,\ldots,a_n])$$$ по модулю $$$10^9+7$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — начальные значения массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел, являющимися ответами для каждого префикса $$$a$$$ по модулю $$$10^9+7$$$.

Пример
Входные данные
3
10
1 2 3 4 5 6 7 8 9 10
11
1 6 9 4 7 4 4 10 3 2 3
4
527792568 502211460 850237282 374773208
Выходные данные
1 3 8 13 46 59 126 149 1174 1311 
1 7 22 26 70 74 150 1303 1306 1308 1568 
527792568 83665723 399119771 773892979
Примечание

Для каждого префикса в первом наборе входных данных возможен следующий массив после применения операций:

  • $$$[1]$$$: сумма равна $$$1$$$;
  • $$$[1, 2]$$$: сумма равна $$$3$$$;
  • $$$[1, 1, 6]$$$: сумма равна $$$8$$$;
  • $$$[1, 1, 3, 8]$$$: сумма равна $$$13$$$;
  • $$$[1, 1, 3, 1, 40]$$$: сумма равна $$$46$$$;
  • $$$[1, 1, 3, 1, 5, 48]$$$: сумма равна $$$59$$$;
  • $$$[1, 1, 3, 1, 5, 3, 112]$$$: сумма равна $$$126$$$;
  • $$$[1, 1, 3, 1, 5, 3, 7, 128]$$$: сумма равна $$$149$$$;
  • $$$[1, 1, 3, 1, 5, 3, 7, 1, 1152]$$$: сумма равна $$$1174$$$;
  • $$$[1, 1, 3, 1, 5, 3, 7, 1, 9, 1280]$$$: сумма равна $$$1311$$$.