题目描述

整数 $N,K$ と長さ $K$ の数列 $E$ が与えられます。
長さ $N$ の正整数列であって、以下の条件を全て満たすものの総数を $\color{red}{10^9+7}$ で割った余りを求めてください。

• どの要素も平方数でない
• 全要素の積が $\displaystyle\ \prod_{i=1}^{K}\ p_i^{E_i}$ である

但し、

• $p_i$ は小さい方から $i$ 番目の素数を指すものとします。
• ある $2$ つの長さが等しい正整数列 $A,B$ について、 $A$ の $i$ 項目と $B$ の $i$ 項目が異なるような整数 $i$ が存在する時に限り、 $A$ と $B$ は異なる列であるとします。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを整数として出力せよ。

题目大意

给定 $n, k$ 和长为 $k$ 的正整数列 $E$，求长为 $n$ 的满足以下两条件的正整数列数目：

• 数列中没有完全平方数；

• 记 $p_i$ 表示从小到大第 $i$ 个质数，则数列中所有数之积为 $\prod\limits^k_{i=1}p_i^{E_i}$。

答案对 $10^9 + 7$ 取模。

3 2
3 2

15

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

672860525

提示

制約

• 入力は全て整数
• $1\ \le\ N,K,E_i\ \le\ 10000$

Sample Explanation 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$ 個です。

Sample Explanation 2

$\color{red}{10^9+7}$ で割った余りを求めることに注意してください。