Kết thúc đêm biểu diễn tại Hà Nội, ngày hôm sau Jisoo chọn Ninh Bình là địa điểm checkin đầu tiên. Tại đây có ~n~ địa điểm tham quan, địa điểm thứ ~i~ có độ nổi tiếng là ~a_i~. Tuyến xe đưa đón hành khách từ địa điểm thứ ~u~ đến địa điểm thứ ~v~ tồn tại khi và chỉ khi ~u < v~ và hai số ~a_u, a_v~ không nguyên tố cùng nhau.

Jisoo đang đứng tại địa điểm tham quan đầu tiên và cô muốn địa điểm cuối cùng mình đến là địa điểm ~n~. Trí tò mò khơi gợi cô đếm số cách khác nhau để lựa chọn và sắp xếp các tuyến xe để tạo thành đường đi từ địa điểm đầu tiên đến cuối cùng. Bạn hãy giúp Jisoo nhé.

Yêu cầu: Tính số cách đi từ địa điểm 1 đến địa điểm ~n~, lấy dư cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~) – số địa điểm tham quan tại Ninh Bình.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~2 \le a_i \le 10^6~).

Output

• Gồm một dòng duy nhất là đáp án của bài toán, chỉ lấy dư cho ~10^9 + 7~.