Number Sequence

Time Limit: 10000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Given a number sequence b1,b2…bn.
Please count how many number sequences a1,a2,...,an satisfy the condition that a1*a2*...*an=b1*b2*…*bn (ai>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 b1, b2,...,bn(1<bi<=1000000, b1*b2*…*bn<=1025).

Output

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

Sample Input

2 3 4

Sample Output

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

Hint

zhuyuanchen520

Source

2012 Multi-University Training Contest 10

提交代码