不含平方数的序列

题目描述

给定整数 $N$、$K$,以及长度为 $K$ 的序列 $E$。

求满足以下条件的、由正整数组成的长度为 $N$ 的序列的数量,对 $10^9+7$ 取模:

• 没有任何一个元素是平方数;
• 所有元素的乘积等于 $\displaystyle \prod_{i=1}^{K} p_i^{E_i}$。

这里,$p_i$ 表示第 $i$ 小的素数。

两个长度相同、由正整数组成的序列 $A$ 和 $B$,当且仅当存在整数 $i$ 使得两者的第 $i$ 项不同时,被视为不同的序列。

输入格式

输入按以下格式从标准输入给出:

$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

请务必输出对 $10^9+7$ 取模后的答案。

数据范围

• 输入中的所有值都是整数。
• $1 \le N,K,E_i \le 10000$