题目描述

给定整数 $N$ 和 $K$，以及一个长度为 $K$ 的序列 $E$。
找到满足以下条件的长度为 $N$ 的正整数序列的数量（对 $\\color{red}{10^9+7}$ 取模）：

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

这里，

• $p_i$ 表示第 $i$ 个最小的素数。
• 如果两个长度相同的正整数序列 $A$ 和 $B$ 只有在存在一个整数 $i$，使得 $A$ 和 $B$ 的第 $i$ 个元素不同的情况下才认为它们是不同的。

约束条件

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

输入

从标准输入读入数据，输入格式如下：

$N$ $K$ $E_1$ $E_2$ $\ldots$ $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}$ 取模。