#2137. submultiple

内存限制:259 MiB 时间限制:10 Sec

题目描述

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

输入格式

第一行输入N,K。N表示M由前N小的素数组成。接下来N行,第i+1行有一个正整数Pi,表示第Ai小的素数 有 Pi次。等式:

输出格式

输出一个数,表示答案。只需输出最后答案除以1000000007的余数。

样例

样例输入


			
2 3
1
3

样例输出


			
900
【样例说明】
M=2^1*3^3=54
M的约数有1,2,3,6,9,18,27,54.约数个数分别为1,2,2,4,3,6,4,8.
Answer=1^3+2^3+2^3+4^3+3^3+6^3+4^3+8^3=900


编号 N K Pi<=
1 50 3 10000
2 50 100 10000
3 50 20101125 10000
4 999 17651851 100000
5 5000 836954247 100000
6 4687 1073741823 100000
7 4321 123456789 100000
8 5216 368756432 100000
9 8080 2^31-1 100000
10 10086 3 2^63-1
11 64970 3 2^63-1
12 71321 3 2^63-1
13 350 5 2^31-1
14 250 6 2^31-1
15 110 7 2^31-1
16 99 8 2^31-1
17 80 9 2^31-1
18 70 10 2^31-1
19 60 11 2^31-1
20 50 12 2^31-1

数据范围与提示