Ayrat has number $*n*$, represented as it's prime factorization $*p*_{*i*}$ of size $*m*$, i.e. $*n* = *p*_{1}·*p*_{2}·...·*p*_{*m*}$. Ayrat got secret information that that the product of all divisors of $*n*$ taken modulo $10^{9} + 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* ≤ 200 000$) — the number of primes in factorization of $*n*$.

The second line contains $*m*$ primes numbers $*p*_{*i*}$ ($2 ≤ *p*_{*i*} ≤ 200 000$).

Output

Print one integer — the product of all divisors of $*n*$ modulo $10^{9} + 7$.

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$.