Tổng tích OR

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

Example

3
1 2 8

1 9 89 

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.