2370: Multipliers
[Creator : ]
Description
time limit per test
2 secondsmemory limit per test
256 megabytesinput
standard inputoutput
standard outputAyrat has number n, represented as it's prime factorization pi of size m, i.e. n=p1·p2·...·pm. Ayrat got secret information that that the product of all divisors of n taken modulo 109+7 is the password to the secret data base. Now he wants to calculate this value.
Input
The first line of the input contains a single integer m (1≤m≤200000)− the number of primes in factorization of n.
The second line contains m primes numbers pi (2≤pi≤200000).
Output
Print one integer− the product of all divisors of n modulo 109+7.
Examples
Input
2
2 3
Output
36
Input
3
2 3 2
Output
1728
Note
In the first sample n=2·3=6. The divisors of 6 are 1, 2, 3 and 6, their product is equal to 1·2·3·6=36.
In the second sample 2·3·2=12. The divisors of 12 are 1, 2, 3, 4, 6 and 12. 1·2·3·4·6·12=1728.