← 返回题目列表

AtCoder · abc285_h

Ex. 避免平方数

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

分数: 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}.