Cho dãy n số tự nhiên a1, a2, a3, ..., an. Hãy đếm số lượng ước của tích các số của dãy đã cho. Do kết quả lớn nên dua ra số dư của kết quả tìm được chia cho 123456789.
Dữ liệu:
Dòng 1: Số nguyên dương n (n <= 3 * 105)
Dòng 2: Dãy n số nguyên a1, a2, a3, ..., an (ai <= 3 * 10 ^ 6)
Kết quả: Kết quả đếm được
Ví dụ:
Input
4
Output
Giải thích
10
Tích các số là 48 với các ước là 1,2,3 4, 6, 8, 12, 16, 24 và 48
2234
Giới hạn: Gọi T = a * a2 a3 *...* an.
20% test: n <= 10 a_{i} <= 10 ^ 3 và T <= 10 ^ 6
20% test: n <= 10 ai <= 103 và T <= 10 ^ 12
20% test: 10 < n <= 1000 không quá 103. dãy a gồm các số nguyên đôi một khác nhau và giá trị
20% test: 10 < n <= 1000, ai <= 103
20% test còn lại