Ayrat has number n, represented as it's prime factorization pi of size m, i.e. n=p1 \cdot p2 \cdot ... \cdot 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 \le m \le 200000)- the number of primes in factorization of n.

The second line contains m primes numbers pi (2 \le pi \le 200000).

Print one integer- the product of all divisors of n modulo 109+7.

In the first sample n=2 \cdot 3=6. The divisors of 6 are 1, 2, 3 and 6, their product is equal to 1 \cdot 2 \cdot 3 \cdot 6=36.

In the second sample 2 \cdot 3 \cdot 2=12. The divisors of 12 are 1, 2, 3, 4, 6 and 12. 1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12=1728.