Dãy con nguyên tố cùng nhau

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

Một dãy con (subsequence) không rỗng được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của tất cả các phần tử trong dãy con đó bằng $1$.

Hãy đếm số dãy con nguyên tố cùng nhau của $a$. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo ${10}^9+7$.

Hai dãy con được coi là khác nhau nếu tập chỉ số được chọn khác nhau. Ví dụ, với dãy $[1,1]$ có $3$ dãy con khác nhau: $[1]$ (lấy phần tử thứ nhất), $[1]$ (lấy phần tử thứ hai) và $[1,1]$.

Dữ liệu vào

• Dòng đầu chứa một 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: số dãy con nguyên tố cùng nhau của $a$ theo modulo ${10}^9+7$.

Ràng buộc

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

Ví dụ