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.
