CF2035D Yet Another Real Number Problem

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

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

For each test case, output $ n $ integers representing the answer for each prefix of $ a $ modulo $ 10^9+7 $ .

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