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 \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 翻译