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。