Sau khai giảng năm học mới, tập thể liên khối chuyên Tin năm học \(2023\ –\ 2024\) tham gia các trò chơi tập thể ngoại khóa nhằm giúp các bạn trong liên khối gắn kết với nhau, hỗ trợ nhau trong học tập và rèn luyện. Mỗi lớp tổ chức một trò chơi chung cho cả liên khối. 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\). Ví 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 \(a_{1},\ a_{2},\ \ldots,\ a_{n}\). Gọi \(S\ = \ a_{1} \times a_{2} \times \ldots \times 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},\ \ldots,\ a_{n}\), hãy tìm mật mã của dãy số đã cho.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương \(n\) (1 ≤ \(n\) ≤ 10⁶).

• Dòng thứ hai chứa \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) \(\ (\)\(2 \leq a_{i}\)\(\ \leq \ 10\)⁶) các số ghi cách nhau dấu cách.

Kết quả:

+ Ghi một dòng ghi 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 \(\mathbf{10}^{\mathbf{9}}\mathbf{+ 7.}\)

Ràng buộc:

• \(30\%\) số tests tương ứng với \(30\%\) số điểm của bài có: \(S\ \leq \ 10^{12};\)

• \(20\%\) số tests khác tương ứng với \(20\%\) số điểm của bài có: \(n\ \leq \ 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ụ: