Sau khi ShyWoou đã bắt đầu thanh toán hoá đơn, vì quá nhiều đơn hàng đặt cùng lúc nên máy tính ở Shopee gặp một số vấn đề trục trặc, biết ShyWoou là một thanh niên có tài phá phách lâu năm, nên họ đã nhờ ShyWoou về giải một bài toán hóc búa do máy tính đề ra như sau :
Cho n số nguyên dương a1,a2,a3,...,an.
Gọi T=a1×a2×a3×...×an.
Tính số lượng ước số của T, in ra phần dư sau khi chia lấy dư cho 109+7.
Input
Dòng đầu tiên gồm số nguyên n (n≤105)
Dòng thứ hai gồm n số nguyên ai (1≤ai≤106)
Output
- Một dòng duy nhất là kết quả thoã mãn yêu cầu đề bài.
Sample Input
Copy
3
2 3 6
Sample Output
Copy
9
Giải thích
T=2×3×6=36 có 9 ước số : 1,2,3,4,6,9,12,18,36
Subtask
50% số test có 1≤n≤103.
50% số test còn lại không có điều kiện gì thêm.