← 返回题目列表

Codeforces · 396/A

A. 关于分解成乘数的次数

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

给定一个整数 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 被认为是不同的。