当前没有测试数据。

题目描述

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

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

其中，

• $p_i$表示第$i$个最小的素数。
• 如果两个长度相同的正整数序列$A$和$B$在某个位置上不同，则它们被认为是不同的。

限制条件

• 输入中的所有值均为整数
• $1 \le N,K,E_i \le 10000$

输入

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

$N$ $K$

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

输出

输出一个整数，表示答案。

示例

输入1

3 2
3 2

输出1

15

输入2

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

输出2

672860525

要求将计数对$\color{red}{10^9+7}$取模。