给定一个整数 m,作为整数 a1、a2、... 和 $$(m=\prod_{i=1}^{n}a_{i})$$ 的乘积。您的任务是找出将数字 m 分解为 n 个有序正整数的乘积的不同次数。
答案中还必须考虑输入中给出的 n 个乘积的分解。由于答案可能非常大,因此打印它对 1000000007 (109 + 7) 取模。
输入
第一行包含正整数 n (1 ≤ n ≤ 500)。第二行包含空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。
输出
在一行中打印一个数字 k — 将数字 m 分解为 n 个有序乘数模 1000000007 (109 + 7) 的次数。
示例
输入 #1
1 15
输出 #1
1
输入 #2
3 1 1 2
输出 #2
3
输入 #3
2 5 7
输出 #3
4
注意
在第二个示例中,得到数字 2 的分解,需要三个数字中的任何一个等于 2,其余的等于 1。
在第三个示例中,分解为有序乘数的可能方式为 [7,5]、[5,7]、[1,35]、[35,1]。
将正整数 m 分解为 n 个有序乘数是正整数 b = {b1, b2, ... bn} 的一组,使得 $$m = \prod_{i=1}^{n} b_i$$。如果存在索引 i 使得 bi ≠ ci,则两个分解 b 和 c 被认为是不同的。