On Number of Decompositions into Multipliers

Description:

Input:

The first line contains positive integer n (1 ≤ n ≤ 500). The second line contains space-separated integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Output:

In a single line print a single number k — the number of distinct decompositions of number m into n ordered multipliers modulo 1000000007 (10⁹ + 7).

Sample Input:

1
15

Sample Output:

1

Sample Input:

3
1 1 2

Sample Output:

3

Sample Input:

2
5 7

Sample Output:

4

Note:

In the second sample, the get a decomposition of number 2, you need any one number out of three to equal 2, and the rest to equal 1.

In the third sample, the possible ways of decomposing into ordered multipliers are [7,5], [5,7], [1,35], [35,1].

A decomposition of positive integer m into n ordered multipliers is a cortege of positive integers b = {b₁, b₂, ... b_n} such that . Two decompositions b and c are considered different, if there exists index i such that b_i ≠ c_i.