Cho dãy số nguyên dương: ~a_1, a_2, ..., a_M~. Đặt ~N = a_1 \times a_2 \times ... \times a_M~. Hãy tính số lượng ước của ~N~.

Ví dụ: ~N = 2 \times 3 = 6~. Số lượng ước của ~N~ là ~4~ tức là 6 có ~4~ ước: ~1, 2, 3, 6~.

Input

Dòng đầu chứa số nguyên ~M~

Dòng thứ hai là dãy số nguyên dương ~M~ phần tử: ~a_1, a_2, ..., a_M~ (~1 \leq a_i \leq 10^6~)

Output

Một số nguyên duy nhất là kết quả tính được. Kết quả của bài toán chỉ cần in ra phần dư khi chia cho ~10^9 + 7~.

Sample Test

Input

2
2 3

Output

4

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài có ~N \leq 10^6~;
• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài có ~M \leq 1000~;
• Có ~20\%~ số test khác ứng với ~20\%~ số điểm còn lại của bài.