配点 : $600$ 点

問題文

整数 $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$ は異なる列であるとします。

制約

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

入力

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

$N$ $K$

$E_1$ $E_2$ $\dots$ $E_K$

出力

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

3 2
3 2

15

全要素の積が $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$ 個です。

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

672860525

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