Multipliers

题意翻译

给你一个数，输出其所有因数的乘积。 这个数以质因子乘积的形式给出。 例如第一个样例 $2\times 3=6$，$6$ 的因子有$1,2,3,6$，故答案为 $1\times 2\times 3\times 6=36$。 第二个样例 $2\times 3\times 2=12$，$12$ 的因子有 $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 $ .