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.

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 pi (2 ≤ pi ≤ 200 000).

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.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Multipliers {

    static long mod = 1000000007;

    static long pow(long a, long n) {
        a %= mod;
        long res = 1;
        while (n != 0) {
            if ((n & 1) == 1)
                res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }
    
    static long binaryPow(long a, long q) {
        a %= mod;
        if (q == 0) return 1;
        return ((q % 2 == 1 ? a : 1) * binaryPow(a * a, q / 2)) % mod;
    }


    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        long[] count = new long[200001];
        st = new StringTokenizer(br.readLine());

        int maxPrime = -1;
        for (int i = 0; i < n; i++) {
            int p = Integer.parseInt(st.nextToken());
            count[p]++;
            maxPrime = Math.max(maxPrime, p);
        }
        long currPower = 1;
        long answer = 1;
        for (int i = 0; i <= maxPrime; i++) {
            long prodOfDivs = binaryPow(i, (count[i] * (count[i] + 1)) / 2);
            answer = (long) ((binaryPow(answer, count[i] + 1) % mod) * (binaryPow(prodOfDivs, currPower) % mod));
            currPower = (long) ((currPower) * ((count[i] + 1)) % (mod - 1));
        }
        System.out.println(answer%mod);

    }
}
