102857: [AtCoder]ABC285 Ex - Avoid Square Number

Problem Statement

You are given integers $N$ and $K$, and a sequence $E$ of length $K$.
Find the number, modulo $\color{red}{10^9+7}$, of sequences of length $N$ consisting of positive integers that satisfy the following conditions:

• no element is a square number;
• the product of all elements is $\displaystyle \prod_{i=1}^{K} p_i^{E_i}$.

Here,

• $p_i$ denotes the $i$-th smallest prime.
• Two sequences $A$ and $B$ of the same length consisting of positive integers are considered different if and only if there exists an integer $i$ such that the $i$-th terms of $A$ and $B$ are different.

Constraints

• All values in the input are integers.
• $1 \le N,K,E_i \le 10000$

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

3 2
3 2

Sample Output 1

15

The sequences of length $3$ whose total product is $72=2^3 \times 3^2$ are listed below.

• $(1,1,72)$ and its permutations ($3$ instances) are inappropriate because $1$ is a square number.
• $(1,2,36)$ and its permutations ($6$ instances) are inappropriate because $1$ and $36$ are square numbers.
• $(1,3,24)$ and its permutations ($6$ instances) are inappropriate because $1$ is a square number.
• $(1,4,18)$ and its permutations ($6$ instances) are inappropriate because $1$ and $4$ are square numbers.
• $(1,6,12)$ and its permutations ($6$ instances) are inappropriate because $1$ is a square number.
• $(1,8,9)$ and its permutations ($6$ instances) are inappropriate because $1$ and $9$ are square numbers.
• $(2,2,18)$ and its permutations ($3$ instances) are appropriate.
• $(2,3,12)$ and its permutations ($6$ instances) are appropriate.
• $(2,4,9)$ and its permutations ($6$ instances) are inappropriate because $4$ and $9$ are square numbers.
• $(2,6,6)$ and its permutations ($3$ instances) are appropriate.
• $(3,3,8)$ and its permutations ($3$ instances) are appropriate.
• $(3,4,6)$ and its permutations ($6$ instances) are inappropriate because $4$ is a square number.

Therefore, $15$ sequences satisfy the conditions.

Sample Input 2

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

Sample Output 2

672860525

Be sure to find the count modulo $\color{red}{10^9+7}$.

问题描述

给你整数$N$和$K$，以及长度为$K$的序列$E$。

• 没有元素是平方数；
• 所有元素的乘积为$\displaystyle \prod_{i=1}^{K} p_i^{E_i}$。

其中，

• $p_i$表示第$i$小的质数。
• 由正整数组成的长度相同的序列$A$和$B$被认为不同，仅当存在一个整数$i$，使得$A$和$B$的第$i$项不同。

约束

• 输入中的所有值都是整数。
• $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}$的计数。