Problem Description

Given a number sequence ${A}_{1},{A}_{2}....{A}_{n}$,indicating $N=\prod_{i=1}^{n}{i}^{{A}_{i}}$.What is the product of all the divisors of N?

Input

There are multiple test cases.
First line of each case contains a single integer n.$(1\leq n\leq {10}^{5})$
Next line contains n integers ${A}_{1},{A}_{2}....{A}_{n}$,it's guaranteed not all ${A}_{i}=0$.$(0\leq {A}_{i}\leq {10}^{5})$.
It's guaranteed that $\sum n\leq 500000$.

Output

For each test case, please print the answer module ${10}^{9}+7$ in a line.

4
0 1 1 0
5
1 2 3 4 5

36
473272463