Bạn An đại diện lớp 11 Tin tổ chức trò chơi tìm mật mã như sau: Cho một số nguyên dương x, mật mã của x chính là số lượng ước của x. Vi dụ: x = 8 có bốn ước 1,2, 4, 8 nên mật mã của x là 4.

Trong quá trình tham gia trò chơi thấy bài toán bạn An đưa ra còn đơn giản quá nên bạn Sơn mở rộng bài toán như sau: Cho n số nguyên dương a1, a2,..., an.

Gọi ~S = a_1 × a_2 × … × a_n~ yêu cầu tìm mật mã của S.

Ví dụ: với dãy số { 2, 8, 4}, S = 64 có bảy ước 1, 2, 4, 8, 16, 32, 64. Vậy mật mã của dãy là 7.

Yêu cầu: Cho dãy số ~a_1, a_2, ..., a_n~, hãy tìm mật mã của dãy số đã cho.

Dữ liệu vào gồm:

• Dòng đầu tiên chứa số nguyên dương n ~(1 ≤ n ≤ 10^6)~,
• Dòng thứ hai chứa n số nguyên ~a_1, a_2,..., a_n~ ~(2 ≤ a_i ≤ 10^6)~ các số ghi cách nhau dấu cách.

Kết quả: ghi ra một số là mật mã tìm được, tương ứng với số lượng ước của dãy khi chia lấy phần dư cho ~10^9+7~.

Ràng buộc:

• 30% số tests tương ứng với 30% số điểm của bài có: ~S ≤ 10^{12}~;
• 20% số tests khác tương ứng với 20% số điểm của bài có: n ≤ 1000 và ~a_i~ là số nguyên tố;
• 50% số tests còn lại tương ứng với 50% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

Input

3
2 8 4

Output

7

Nguồn