3909. 幻化成风

【题目描述】

有一个长为 $m$ 的序列 $\{a_i\}$ 和一个 $n$，其中 $n!$ 可以用下列方式表示：

$$n!=\prod {b_i}^{a_i}$$

其中 $\{b_i\}$ 中的数两两不同。

两种表示方式不同当且仅当集合 $\{(b_i, a_i)\}$ 不同。现在你需要对不同表示方式计数。答案对 $10^9+7$ 取模。

【输入格式】

第一行输入两个整数 $n, m$。

第二行输入 $m$ 个正整数 $a_i$。

【输出格式】

输出不同表示方式个数对 $10^9+7$ 取模的结果。

【样例输入 1】

10 6
1 2 2 3 3 3

【样例输出 1】

2

【样例输入 2】

20 6
1 2 2 3 3 3

【样例输出 2】

41680

【样例说明】

$$10! = 42\times 5^2\times 4^2\times 3^3\times 2^3\times 1^3 = 21 \times 5^2\times 2^2\times 4^3\times 3^3\times 1^3$$

【数据规模与约定】

对于 20% 的数据，$1\le n\le 10, 1\le m, \sum a_i\le 5$。

对于 60% 的数据，$1\le n\le 10^3, 1\le m\le 10, 1\le \sum a_i\le 30$。

对于 100% 的数据，$1\le n\le 10^4, 1\le m, \sum a_i\le 30$。

【来源】

2019 山东一轮省集。