Cho dãy \(a_1,a_2,…,a_n\). Tính số lượng dãy con không rỗng của dãy \(a\) sao cho \(GCD\) của dãy con đó bằng \(1\).

Input

• Dòng 1 chứa số nguyên \(n(1 ≤ n ≤ 10^5)\)

• Dòng 2 chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤ 10^5) \)

Output

• Số lượng dãy con tìm được. Kết quá lấy số dư của số lượng dãy chia cho \(10^9+7\)

Sample Input

3
1 2 3

Sample Output

5

Ràng buộc:

• Subtask 1 : \(n,a_i ≤ 5\)

• Subtask 2 : \(n,a_i ≤ 8\)

• Subtask 1 : Không có ràng buộc gì thêm