[ABC285Ex] Avoid Square Number

给定 $n, k$ 和长为 $k$ 的正整数列 $E$，求长为 $n$ 的满足以下两条件的正整数列数目： - 数列中没有完全平方数； - 记 $p_i$ 表示从小到大第 $i$ 个质数，则数列中所有数之积为 $\prod\limits^k_{i=1}p_i^{E_i}$。 答案对 $10^9 + 7$ 取模。

[problemUrl]: https://atcoder.jp/contests/abc285/tasks/abc285_h 整数 $ 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 $

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

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} $ で割った余りを求めることに注意してください。