题目描述

设函数 $g(N)$ 表示 $N$ 的约数个数。现在给出一个数 $M$，求出所有 $M$ 的约数 $x$ 的 $g(x)$ 的 $K$ 次方和。

输入格式

第一行输入 $N,K$。$N$ 表示 $M$ 由前 $N$ 小的素数组成。

接下来 $N$ 行，第 $i+1$ 行有一个正整数 $P_i$ ，表示第 $i$ 小的素数有 $P_i$ 次。

$\displaystyle M=\prod_{i = 1}^{N}\mathrm{prime}_{i}^{P_i}$，其中 $\mathrm{prime}_{i}$ 表示小于 $2^{31}-1$ 的素数集合中第 $i$ 小的数。

输出格式

输出一个数，表示答案。只需输出最后答案除以 $10^9+7$ 的余数。

2 3
1
3

900

样例说明

$M=2^1\times 3^3=54$，$M$ 的约数有 $1,2,3,6,9,18,27,54$。约数个数分别为$1,2,2,4,3,6,4,8$。

$\mathrm{Answer}=1^3+2^3+2^3+4^3+3^3+6^3+4^3+8^3=900$

数据规模与约定

保证 $N,K,P_i$ 均大于 $0$。