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\).