题目描述
令 $H(x)=\sum_{i=0}^{K}A_ix^i$
令 $G(x)=\sum_{d|x}H(d)$
令 $$ F(x,y)=\left\{ \begin{array}{lcl} G(x)&&\mathrm{if}\ y=1,\\ \sum_{d|x}F(d,y-1)G(\frac x d)&&\mathrm{otherwise}. \end{array}\right. $$
求 $\sum_{i=1}^N F(i,M)$.
输入格式
第一行三个整数,分别为 $N, M, K$.
第二行 $K$ 个整数,第 i 个为 $A_{i−1}$ .
输出格式
一个整数表示答案,模 $998244353$.
样例输入
10 2 1
1
样例输出
89
子任务
对所有数据,保证 $1 ≤ N, M ≤ 10^9 , 0 ≤ K ≤ 50, 0 ≤ A_i < 998244353$.
$N ≤ 10^5 , M ≤ 2$ ( 10 分)
$N ≤ 10^5$ ( 15 分)
$N ≤ 10^7$ ( 15 分)
$M ≤ 2$ ( 15 分)
$M ≤ 30$ ( 15 分)
$N ≤ 10^8$ ( 15 分)
没有特殊性质( 15 分)
