Mùa đông đã đến

Cho một dãy gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$.

Một dãy chỉ số $i_1<i_2<\cdots <i_k$ (với $k\ge 1$) được gọi là một nhóm nếu

$$gcd(a_{i_1},a_{i_2},\dots ,a_{i_k})>1.$$

Sức mạnh của một nhóm bằng $k·gcd(a_{i_1},a_{i_2},\dots ,a_{i_k})$, trong đó $k$ là số phần tử của nhóm.

Hãy tính tổng sức mạnh của tất cả các nhóm có thể có. Vì kết quả có thể rất lớn, in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng sức mạnh của tất cả các nhóm, lấy dư cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_i\le {10}^6$

Ví dụ