← 返回题目列表

Codeforces · 615/D

D. 乘数

中文机器翻译题面 查看原题

Ayrat 的编号为 n,表示为大小为 m 的质因数分解 pi,即 n = p1·p2·...·pm。 Ayrat 得到秘密信息,n 的所有除数模 109 + 7 的乘积就是秘密数据库的密码。现在他要计算这个值。

输入

输入的第一行包含一个整数 m (1 ≤ m ≤ 200 000) — n 因式分解中的素数数量。

第二行包含 m 个素数 pi (2 ≤ pi ≤ 200 000)。

输出

打印一个整数 — n 模 109 + 7 的所有除数的乘积。

示例

输入 #1

2
2 3

输出 #1

36

输入 #2

3
2 3 2

输出 #2

1728

注意

在第一个样本中,n = 2·3 = 6。6 的约数为 1、2、3 和 6,它们的乘积等于 1·2·3·6 = 36。

在第二个示例中,2·3·2 = 12。12 的约数为 1、2、3、4、6 和 12。1·2·3·4·6·12 = 1728。