Ayrat 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.
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).
Print one integer− the product of all divisors of n modulo 109+7.
2
2 3
36
3
2 3 2
1728
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.