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\)