分数: 600 点
问题陈述
给你整数 N 和 K,以及一个序列 E 长度 K.
求模数 \color{red}{10^9+7},长度序列 N 由满足以下条件的正整数组成:
- 没有元素是平方数;
- 所有元素的乘积是 \displaystyle \prod_{i=1}^{K} p_i^{E_i}.
在这里,
- p_i 表示 i- 第一个最小的素数。 当且仅当存在一个整数时,由正整数组成的相同长度的
- 两个序列 A 和 B 被认为是不同的 i 这样 i第一项 A 和 B 不同。
约束
- 输入中的所有值都是整数。
- 1 \le N,K,E_i \le 10000
输入
输入由标准输入按以下格式给出:
N K E_1 E_2 \dots E_K
输出
将答案打印为整数。
示例输入 1
3 2 3 2
示例输出 1
15
长度序列 3 其总产品为 下面列出了 72=2^3 \times 3^2 。
- (1,1,72) 及其排列(3 实例)不合适,因为 1 是一个平方数。
- (1,2,36) 及其排列(6 实例)不合适,因为 1 和 36 是平方数。
- (1,3,24) 及其排列(6 实例)不合适,因为 1 是一个平方数。
- (1,4,18) 及其排列(6 实例)不合适,因为 1 和 4 是平方数。
- (1,6,12) 及其排列(6 实例)不合适,因为 1 是一个平方数。
- (1,8,9) 及其排列(6 实例)不合适,因为 1 和 9 是平方数。
- (2,2,18) 及其排列(3 实例)是适当的。
- (2,3,12) 及其排列(6 实例)是适当的。
- (2,4,9) 及其排列(6 实例)不合适,因为 4 和 9 是平方数。
- (2,6,6) 及其排列(3 实例)是适当的。
- (3,3,8) 及其排列(3 实例)是适当的。
- (3,4,6) 及其排列(6 实例)不合适,因为 4 是一个平方数。
因此, 15 序列满足条件。
示例输入 2
285 10 3141 5926 5358 9793 2384 6264 3383 279 5028 8419
示例输出 2
672860525
一定要找到计数模数 \color{red}{10^9+7}.