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 ba
se. Now he wants to calculate this value.
Ayrat有数字n，表示为大小为m的质因数分解pi，即n=p1·p2·…·pm。Ayrat得到了秘密信息，n的所有因数对109+7取模后的乘积就是秘密数据库的密码。现在他想计算这个值。
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
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.