Given an array $Arr$ of $N$ positive integers.
Omega of a number $X$ is defined as the set of prime numbers that divide $X$.
Example:
Omega of 10 is [2,5], Omega of 1 is [], and Omega of 18 is [2,3].
The beauty of the array is defined as the product of the frequency of different omegas occurring in the array. Return the beauty of the given array (in Modulo $10^9 +7$).

Input format

• The first line contains an integer $N$, where $N$ denotes the size of the array $Arr$.
• The second line contains $N$ space-separated integers denoting array $Arr$.

Output format

• Print the beauty of the given array.

Constraints

• $1\leq N \leq 10^6$
• $1 \leq Arr[i] \leq 10^5$