D. Yet Another Real Number Problemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThree r there are's in strawberry.You are given an array $$$b$$$ of length $$$m$$$. You can perform the following operation any number of times (possibly zero): Choose two distinct indices $$$i$$$ and $$$j$$$ where $$$\bf{1\le i < j\le m}$$$ and $$$b_i$$$ is even, divide $$$b_i$$$ by $$$2$$$ and multiply $$$b_j$$$ by $$$2$$$. Your task is to maximize the sum of the array after performing any number of such operations. Since it could be large, output this sum modulo $$$10^9+7$$$.Since this problem is too easy, you are given an array $$$a$$$ of length $$$n$$$ and need to solve the problem for each prefix of $$$a$$$.In other words, denoting the maximum sum of $$$b$$$ after performing any number of such operations as $$$f(b)$$$, you need to output $$$f([a_1])$$$, $$$f([a_1,a_2])$$$, $$$\ldots$$$, $$$f([a_1,a_2,\ldots,a_n])$$$ modulo $$$10^9+7$$$ respectively.InputThe first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the starting values of array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.OutputFor each test case, output $$$n$$$ integers representing the answer for each prefix of $$$a$$$ modulo $$$10^9+7$$$.ExampleInput3101 2 3 4 5 6 7 8 9 10111 6 9 4 7 4 4 10 3 2 34527792568 502211460 850237282 374773208Output1 3 8 13 46 59 126 149 1174 1311
1 7 22 26 70 74 150 1303 1306 1308 1568
527792568 83665723 399119771 773892979
NoteFor each prefix in the first example, a possible array after operations is: $$$[1]$$$ and the sum is $$$1$$$; $$$[1, 2]$$$ and the sum is $$$3$$$; $$$[1, 1, 6]$$$ and the sum is $$$8$$$; $$$[1, 1, 3, 8]$$$ and the sum is $$$13$$$; $$$[1, 1, 3, 1, 40]$$$ and the sum is $$$46$$$; $$$[1, 1, 3, 1, 5, 48]$$$ and the sum is $$$59$$$; $$$[1, 1, 3, 1, 5, 3, 112]$$$ and the sum is $$$126$$$; $$$[1, 1, 3, 1, 5, 3, 7, 128]$$$ and the sum is $$$149$$$; $$$[1, 1, 3, 1, 5, 3, 7, 1, 1152]$$$ and the sum is $$$1174$$$; $$$[1, 1, 3, 1, 5, 3, 7, 1, 9, 1280]$$$ and the sum is $$$1311$$$.