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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Set;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author whhone
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    long MOD = 1000000007;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      int m = in.nextInt();
      int[] a = in.nextIntArray(m);
      MultiSet<Integer> ms = new MultiSet<Integer>();

      for (int i = 0; i < m; ++i) {
        ms.add(a[i]);
      }

      long[] l = new long[m];
      long[] r = new long[m];

      Integer[] ps = new Integer[ms.size()];
      ps = ms.elementSet().toArray(ps);
      for (int i = 0; i < ps.length; ++i) {
        long count = ms.count(ps[i]);

        if (i == 0) {
          l[i] = (count + 1);
        } else {
          l[i] = (l[i - 1] * (count + 1)) % (MOD - 1);
        }
      }

      for (int i = ps.length - 1; i >= 0; --i) {
        long count = ms.count(ps[i]);

        if (i == ps.length - 1) {
          r[i] = (count + 1);
        } else {
          r[i] = (r[i + 1] * (count + 1)) % (MOD - 1);
        }
      }

      long ans = 1;
      for (int i = 0; i < ps.length; ++i) {
        int p = ps[i];
        long count = ms.count(p);
        long tmp = 1;
        if (i > 0) tmp *= l[i - 1];
        if (i < ps.length - 1) tmp *= r[i + 1];
        tmp %= (MOD - 1);
        long counts = (count * (count + 1) / 2) % (MOD - 1);
        ans = (ans * Modular.on(MOD).power(p, (counts * tmp) % (MOD - 1))) % MOD;
      }
      out.println(ans);
    }

  }

  static class OutputWriter extends PrintWriter {
    public OutputWriter(OutputStream stream) {
      super(stream);
    }

    public OutputWriter(Writer writer) {
      super(writer);
    }

  }

  static class MultiSet<T> {
    HashMap<T, Integer> hm;

    public MultiSet() {
      hm = new HashMap<T, Integer>();
    }

    public void add(T object) {
      add(object, 1);
    }

    public void add(T object, int occurrences) {
      if (contains(object)) {
        hm.put(object, hm.get(object) + occurrences);
      } else {
        hm.put(object, occurrences);
      }
    }

    public boolean contains(T object) {
      return hm.containsKey(object);
    }

    public Set<T> elementSet() {
      return hm.keySet();
    }

    public int count(T object) {
      return hm.getOrDefault(object, 0);
    }

    public int size() {
      return hm.size();
    }

  }

  static class Modular {
    long MOD;

    public static Modular on(long mod) {
      return new Modular(mod);
    }

    private Modular(long mod) {
      this.MOD = mod;
    }

    public long power(long a, long b) {
      if (b == 0) {
        return 1;
      }
      long val = power(a, b / 2);
      if (b % 2 == 0) {
        return (val * val) % MOD;
      } else {
        return (val * (val * a % MOD)) % MOD;
      }
    }

  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String nextLine() {
      try {
        return reader.readLine();
      } catch (IOException e) {
        throw new RuntimeException(e);
      }
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        tokenizer = new StringTokenizer(nextLine());
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; ++i) {
        a[i] = nextInt();
      }
      return a;
    }

  }
}

