Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là tính số lượng tập con không rỗng mà bitwise and của các phần tử bằng \(k\) với mỗi \(k = 0, 1,\dots, n\).

Input

Dòng đầu tiên chứa một số nguyên \(n\): kích thước của mảng.

Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2,\dots, a_n\): các phần tử của mảng.

Output

In ra \(n + 1\) số nguyên như mô tả ở trên, lấy modulo \(10^9 + 7\).

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

• \(0 \le a_i \le n\)

Example

4
3 1 3 4

7 4 0 3 1