Multipliers

题意翻译

给你一个数,输出其所有因数的乘积。 这个数以质因子乘积的形式给出。 例如第一个样例$2\times 3=6$,$6$的因子有$1,2,3,6$,故答案为$1\times 2\times 3\times 6=36$。 第二个样例$2\times 3\times 2=12$,$6$的因子有$1,2,3,4,6,12$,故答案为$1\times 2\times 3\times 4\times 6\times 12=1728$。 由于答案可能过大,对$10^9+7$取模。 输入: 第一行一个正整数n,代表质因子的个数 第二行n个正整数,为质因子。 注意同一个质因子可能出现多次。 输出: 其所有因子的乘积并取模。

题目描述

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.

输入输出格式

输入格式


The first line of the input contains a single integer $ m $ ( $ 1<=m<=200000 $ ) — the number of primes in factorization of $ n $ . The second line contains $ m $ primes numbers $ p_{i} $ ( $ 2<=p_{i}<=200000 $ ).

输出格式


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

输入输出样例

输入样例 #1

2
2 3

输出样例 #1

36

输入样例 #2

3
2 3 2

输出样例 #2

1728

说明

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