Problem Description

Count the number of sets of divisors of $ N $ that contain pairs that are not coprime.

Input Format

$ N $ is the product of $ M $ natural numbers $ A_1, A_2, ..., A_{M-1}, A_M $, and is given from standard input in the following format:

$ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_{M-1} $ $ A_M $

Output Format

Output the number of sets satisfying the condition modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

1
6

Sample Output #1

6

Sample Input #2

2
2 3

Sample Output #2

6

Sample Input #3

10
16808 282475250 622650074 984943659 144108931 470211273 101027545 457850879 458777924 7237710

Sample Output #3

820588505

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq M \leq 1,000$
• $1 \leq A_i \leq 10^9$

Sample Explanation 1

When $ N = 6 $, the sets $ (2, 6), (3, 6), (2, 3, 6), (1, 2, 6), (1, 3, 6), (1, 2, 3, 6) $ satisfy the condition, totaling 6 sets.

Sample Explanation 2

$N = 2 \times 3 = 6$, which is the same as Sample Input/Output #1.

Sample Explanation 3

Be sure to find the remainder modulo $ 10^9+7 $.

见题面 Input 部分

见题面 Output 部分