Hệ thống giám sát điện năng của nhà trường gồm ~n~ thiết bị đo đặt tại các giảng đường, đánh số từ ~1~ đến ~n~. Thiết bị thứ ~i~ gửi số liệu về máy chủ theo chu kỳ ~a_i~ giây.

Một nhóm thiết bị là một tập hợp gồm ít nhất một thiết bị; hai nhóm là khác nhau nếu có một thiết bị thuộc nhóm này mà không thuộc nhóm kia, kể cả khi các chu kỳ trong hai nhóm giống hệt nhau. Một nhóm được gọi là đồng bộ nếu ước chung lớn nhất của chu kỳ của tất cả các thiết bị trong nhóm bằng ~1~; nói riêng, nhóm chỉ gồm một thiết bị ~i~ là đồng bộ khi và chỉ khi ~a_i = 1~.

Yêu cầu

Hãy đếm số nhóm đồng bộ. Vì kết quả có thể rất lớn, chỉ cần đưa ra phần dư của nó khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~n~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~, các số cách nhau bởi dấu cách.

Kết quả ra

Ghi ra một số nguyên duy nhất là số nhóm đồng bộ sau khi lấy phần dư cho ~10^9 + 7~.

Ràng buộc

~1 \le n \le 2 \cdot 10^5~; ~1 \le a_i \le 10^6~.

• Subtask 1 (15% số điểm – test 01–05): ~n \le 20~;
• Subtask 2 (20% số điểm – test 06–10): ~a_i \le 100~;
• Subtask 3 (20% số điểm – test 11–14): mọi ~a_i~ đều là số nguyên tố;
• Subtask 4 (45% số điểm – test 15–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

4
2 3 4 6

Kết quả ra mẫu 1

6

Dữ liệu vào mẫu 2

3
1 5 5

Kết quả ra mẫu 2

4

Giải thích

Ví dụ 1: có ~6~ nhóm đồng bộ, viết theo chu kỳ của các thiết bị trong nhóm là ~\{2,3\}~, ~\{3,4\}~, ~\{2,3,4\}~, ~\{2,3,6\}~, ~\{3,4,6\}~ và ~\{2,3,4,6\}~. Ví dụ 2: có ~4~ nhóm đồng bộ, viết theo số thứ tự của các thiết bị là ~\{1\}~, ~\{1,2\}~, ~\{1,3\}~ và ~\{1,2,3\}~; hai nhóm ~\{1,2\}~ và ~\{1,3\}~ có các chu kỳ giống nhau nhưng vẫn là hai nhóm khác nhau.