Một dãy con khác rỗng \(a_{i_1},\ a_{i_2},\ldots,\ a_{i_k}\) đượ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 bằng \(1\).

Cho dãy \(a\) chứa \(n\) số nguyên dương, hãy tính số dãy con nguyên tố cùng nhau của nó (dãy con có thể gồm các phần tử không liên tiếp). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9+7\).

Hai dãy con được tính là khác nhau nếu tồn tại một chỉ số được chọn ở dãy con này mà không được chọn ở dãy con kia. Ví dụ, trong dãy \([1,\ 1]\) có \(3\) dãy con khác nhau: \([1]\), \([1]\), \([1,\ 1]\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\ (1\leq n\leq10^5)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,\ a_2,\ldots,\ a_n\ (1\leq a_i\leq10^5)\).

Output

• In ra số dãy con nguyên tố cùng nhau của \(a\) sau khi mod \(10^9+7\).

Ví dụ

Sample input 1

3
1 2 3

Sample output 1

5

Sample input 2

4
1 1 1 1

Sample output 2

15

Sample input 3

7
1 3 5 15 3 105 35

Sample output 3

100