Problem Description

Given a number sequence b₁,b₂…b_n.
Please count how many number sequences a₁,a₂,...,a_n satisfy the condition that a₁*a₂*...*a_n=b₁*b₂*…*b_n (a_i>1).

Input

The input consists of multiple test cases.
For each test case, the first line contains an integer n(1<=n<=20). The second line contains n integers which indicate b₁, b₂,...,b_n(1<b_i<=1000000, b₁*b₂*…*b_n<=10²⁵).

Output

For each test case, please print the answer module 1e9 + 7.

2
3 4

4

Hint

For the sample input, P=3*4=12.
Here are the number sequences that satisfy the condition:
2 6
3 4
4 3
6 2