Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

As Roy grew older, his love for mathematics only intensified. He excelled in school, dazzling his teachers and classmates with his knack for solving even the most challenging problems. He participated in math competitions and always emerged victorious, earning him the admiration of his peers and teachers alike.

You are given an array A with n length.You have to find out the total divisor of N.

N can be represent ,A1 * A2 * A3 * ... An = N;

Answer can be very large so print it modulo by \(10^9+7\);

Input

In the first line an integer n which represent length of the array.

In the second line an array A with n length.

\(1<=n<= 5 * 10^5\)

\(1<=A[]<=10^6\)

Output

print the total divisor of N by Modulo \(10^9+7\).

Sample

5
1 1 4 2 4

6

N = 1 * 1* 4* 2* 4 = 32.
Total divisor of N is 6 = {1, 2, 4, 8, 16, 32}.