AT_abc285_h [ABC285Ex] Avoid Square Number

题目描述

给定整数 $N,K$ 和一个长度为 $K$ 的数列 $E$。
请计算满足以下所有条件的长度为 $N$ 的正整数序列的总数，并将答案对 $10^9+7$ 取模后输出。

• 每个元素都不是完全平方数。
• 所有元素的乘积等于 $\displaystyle\prod_{i=1}^{K} p_i^{E_i}$。

其中，

• $p_i$ 表示从小到大第 $i$ 个质数。
• 对于两个长度相等的正整数序列 $A,B$，如果存在某个整数 $i$ 使得 $A$ 的第 $i$ 项与 $B$ 的第 $i$ 项不同，则 $A$ 与 $B$ 被认为是不同的序列。

输入格式

输入通过标准输入按以下格式给出。

$N$ $K$ $E_1$ $E_2$ $\dots$ $E_K$

输出格式

请输出一个整数作为答案。

输入输出样例 #1

输入 #1

3 2
3 2

输出 #1

15

输入输出样例 #2

输入 #2

285 10
3141 5926 5358 9793 2384 6264 3383 279 5028 8419

输出 #2

672860525

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N,K,E_i \leq 10000$

样例解释 1

所有元素的乘积为 $72=2^3 \times 3^2$ 的长度为 $3$ 的数列如下：

• $(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

请注意，答案需要对 $10^9+7$ 取模。

由 ChatGPT 4.1 翻译