#P2137. submultiple

    ID: 1160 传统题 1000ms 259MiB 尝试: 324 已通过: 133 难度: 6 上传者: 标签>CF2100提高约数个数乘积公式快速幂一维前缀和连续点值插值阶乘逆元预处理前后缀分解阈值划分大小情况

submultiple

题目描述

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

输入格式

第一行输入 N,KN,K。NN 表示 MM 由前 NN 小的素数组成。

接下来 NN 行,第 i+1i+1 行有一个正整数 PiP_i ,表示第 ii 小的素数有 PiP_i 次。

$\displaystyle M=\prod_{i = 1}^{N}\mathrm{prime}_{i}^{P_i}$,其中 primei\mathrm{prime}_{i} 表示小于 231−12^{31}-1 的素数集合中第 ii 小的数。

输出格式

输出一个数,表示答案。只需输出最后答案除以 109+710^9+7 的余数。

2 3
1
3
900

样例说明

M=21×33=54M=2^1\times 3^3=54,MM 的约数有 1,2,3,6,9,18,27,541,2,3,6,9,18,27,54。约数个数分别为1,2,2,4,3,6,4,81,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,PiN,K,P_i 均大于 00。

编号 NN KK Pi≤P_i\le
11 5050 33 10410^4
22 100100
33 2010112520101125
44 999999 1765185117651851 10510^5
55 5×1035\times 10^3 836954247836954247
66 46874687 10737418231073741823
77 43214321 123456789123456789
88 52165216 368756432368756432
99 80808080 231−12^{31}-1
1010 1008610086 33 263−12^{63}-1
1111 6497064970
1212 7132171321
1313 350350 55 231−12^{31}-1
1414 250250 66
1515 110110 77
1616 9999 88
1717 8080 99
1818 7070 1010
1919 6060 1111
2020 5050 1212