Để chuẩn bị tốt cho vai diễn người nhện của mình, Tôm Hà Lan quyết định luyện tập đi dây. Khu phố anh đang ở có \(n\) tòa nhà, tòa nhà thứ \(i\) cao \(a_i\) mét . Xuất phát từ tòa nhà đầu tiên, Tôm Hà Lan muốn đu đến tòa nhà thứ \(n\) . Biết rằng anh ta chỉ có thể đu từ tòa nhà \(i\) tới toà nhà \(j\) nếu \(i<j\) và \(\gcd(a_i,a_j)>1\), hãy đếm số cách đu dây có thể của anh chàng này.

Input

• Dòng đầu tiên là số nguyên dương \(n\) \((n \le 2 \times 10^5)\).
• Dòng thứ hai là \(n\) số nguyên dương \(a_i\) \((a_i \le 5 \times 10^5)\).

Output

• Gồm một dòng duy nhất là số cách đu dây chia dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\): \(n \le 1000\).
• Subtask \(2\): Không có thêm điều kiện

Example

5
2 6 3 4 6

5

5
4 196 2662 2197 121

2

7
3 6 8 9 11 12 20

7