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 \(a_1, a_2, a_3, ..., a_n\).

• Gọi \(T = a_1 \times a_2 \times a_3 \times ... \times a_n\).

• Tính số lượng ước số của \(T\), in ra phần dư sau khi chia lấy dư cho \(10^9 + 7\).

Input

• Dòng đầu tiên gồm số nguyên \(n\) \((n \leq 10^5)\)

• Dòng thứ hai gồm \(n\) số nguyên \(a_i\) \((1 \leq a_i \leq 10^{6})\)

Output

• Một dòng duy nhất là kết quả thoã mãn yêu cầu đề bài.

Sample Input

3
2 3 6

Sample Output

9

Giải thích

\( T = 2 \times 3 \times 6 = 36\) có \(9\) ước số : \(1, 2, 3, 4, 6, 9, 12, 18, 36\)

Subtask

• \(50\%\) số test có \(1 \leq n \leq 10^3\).

• \(50\%\) số test còn lại không có điều kiện gì thêm.