Cho một dãy \(n\) số nguyên dương \(a_0, a_1, \ldots, a_{n-1}\).

Với mọi \(U\) thỏa mãn \(0 \leq U < n\): Tính tổng \(a_i \cdot a_j\) với mọi \(0\leq i,j < n, (i\text{ or }j) \leq U\).

Toán tử or ở đây biểu thị cho toán tử nhị phân OR.

Input

• Dòng đầu chứa số nguyên duy nhất là \(n\) \((1 \leq n \leq 2 \cdot 10^5)\), độ dài mảng \(a\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_0, a_1, \ldots, a_{n-1}\) \((0 < a_{i} \leq 10^7)\).

Output

• In ra \(n\) số nguyên dương trên cùng một dòng duy nhất. Số thứ \(i\) là đáp án cho \(U = i - 1\) khi chia dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^4\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Examples

3
1 2 8

1 9 89

5
2 3 5 5 3

4 25 70 225 246

10
19 18 16 14 16 17 8 15 9 10

361 1369 2233 4489 5353 8020 9412 15129 15552 16896