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à ước chung lớn nhất của các phần tử trong tập con bằng \(k\), với mỗi \(k = 1,\dots, n\).

Dữ liệu vào

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 \(x_1, x_2,\dots, x_n\): các phần tử của mảng.

Dữ liệu ra

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

Constraints

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

• \(1 \le x_i \le n\)

Example

5
5 4 4 2 3

22 4 1 3 1