a (2s 512MB)

定义 $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

2
4 2
4

7

这个样例中，$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$

样例2

25
97 48 24 16 9 7 5 5 4 3 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1
10

287549200

这个样例中，$n=100!$

数据规模

对于所有数据，$1\le m\le 10^3,0\le a_i\le 10^4,1\le k\le30$。

Subtask1 10pts: $m\le 5,a_i\le 5,k\le 5$

Subtask2 10pts: $k=2$

Subtask3 10pts: $k=3$

Subtask4 20pts: $k\le 5$

Subtask5 20pts: $k\le 10$

Subtask6 5pts: $a_i\le 1$

Subtask7 10pts: $a_i\le 2$

Subtask8 10pts: $a_i\le 5$

Subtask9 5pts: 无特殊限制