Tập Con Có GCD Bằng Một

Cho một dãy số nguyên dương, đếm các tập chỉ số không rỗng sao cho gcd của toàn bộ giá trị được chọn bằng $1$.

Một tập chỉ số xác định một dãy con theo thứ tự chỉ số tăng dần. Tập phải chứa ít nhất một chỉ số; hai tập chỉ số khác nhau luôn được tính là hai cách chọn khác nhau.

Input

• Dòng đầu chứa số phần tử $n$.
• Dòng tiếp theo chứa $n$ số nguyên dương $a_i$.

Output

• In số tập chỉ số thỏa mãn theo modulo $1000000007$. Hai cách chọn khác chỉ số được xem là khác nhau.

Constraints

• $1\le n\le 10^5.$
• $1\le a_i\le 10^5.$
• Mọi phép tính kết quả thực hiện modulo $1000000007$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 20$ và $a_i\le 100$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

3
2 3 4

3