U424573 数数

定义 $W(n,k)$ 表示将 $n$ 分解成 $k$ 个不同正整数的乘积的方案数。 现在给定 $n$ 和 $k$，求出 $W(n,k)$。

第一行输入一个正整数 $m$，第二行输入 $m$ 个整数 $a_i$，第三行输入一个正整数 $k$。

令 $n=\prod_{i=1}^{m}{p_i^{a_i}}$，（$p_i$ 是第 $i$ 个质数，$p_1=2,p_2=3,p_3=5,...$）。 输出一个整数 $W(n,k)$，对 $10^9+7$ 取模后的结果。

#### 样例1说明 这个样例中，$n=2^4\times3^2=144$，有如下 $7$ 种方案： $144=1×2×4×18$ $144=1×2×8×9$ $144=1×2×3×24$ $144=1×2×6×12$ $144=1×3×4×12$ $144=1×3×6×8$ $144=2×3×4×6$ #### 数据规模 对于所有数据，$1\le m\le 10^3,0\le a_i\le 10^4,1\le k\le30$。 | $\mathrm {Subtask}$ | 特殊性质 | 总分值 | | :-----------: | :-----------: | :-----------: | | $\mathrm {1}$ | $m\le 5,a_i\le 5,k\le 5$ | $\mathrm {10}$ | | $\mathrm {2}$ | $k=2$ | $\mathrm {10}$ | | $\mathrm {3}$ | $k=3$ | $\mathrm {10}$ | | $\mathrm {4}$ | $k\le 5$ | $\mathrm {20}$ | | $\mathrm {5}$ | $k\le 10$ | $\mathrm {20}$ | | $\mathrm {6}$ | $a_i\le 1$ | $\mathrm {5}$ | | $\mathrm {7}$ | $a_i\le 2$ | $\mathrm {10}$ | | $\mathrm {8}$ | $a_i\le 5$ | $\mathrm {10}$ | | $\mathrm {9}$ | 无 | $\mathrm {5}$ |