Sum

给定非负整数 $n,k$ 与序列 $a_1,a_2,\dots,a_m$ （其中 $m = \lfloor \sqrt n \rfloor$ ）

试求以下表达式对 $998244353$ 取模的值：

$$\sum_{i=1}^na_{v(i)}i^k$$

其中 $v(i)$ 表示 $i$ 最大的平方因子，即 $v(i) = \max\{j|j \in \N^*,j^2 | i\}$。

输入格式

第一行输入两个数 $n,k$。

第二行输入 $m = \lfloor \sqrt n \rfloor$ 个数 $a_1,a_2,\dots,a_m$。

输出格式

一行一个数，表示答案。

样例输入 1

2 1
3

样例输出 1

9

样例解释 1

对 $i = 1,v(i) = 1,a_{v(i)} = 3,a_{v(i)}i^k=3$

对 $i = 2,v(i) = 1,a_{v(i)} = 3,a_{v(i)}i^k = 6$

所以 $\sum_{i=1}^n a_{v(i)}i^k = 9$

样例输入 2

10 5
3 7 6

样例输出 2

974790

样例解释 2

$v(1) \sim v(10)$ 分别为 $1,1,1,2,1,1,1,2,3,1$ ，代入原式可得结果为 $974790$。

样例输入 3 / 样例输出 3

见 down/sum_sample3.in 和 down/sum_sample3.out。该样例满足测试点 $1 \sim 4$ 的限制。

样例输入 4 / 样例输出 4

见 down/sum_sample4.in 和 down/sum_sample4.out。该样例满足测试点 $5 \sim 6$ 的限制。

样例输入 5 / 样例输出 5

见 down/sum_sample5.in 和 down/sum_sample5.out。该样例满足测试点 $11 \sim 12$ 的限制。

样例输入 6 / 样例输出 6

见 down/sum_sample6.in 和 down/sum_sample6.out。该样例满足测试点 $13 \sim 14$ 的限制。

样例输入 7 / 样例输出 7

见 down/sum_sample7.in 和 down/sum_sample7.out。该样例满足测试点 $15 \sim 20$ 的限制。

数据范围

测试点编号	$n \le$	$k \le$	特殊限制
$1 \sim 4$	$10^6$	$10^9$
$5 \sim 6$	$10^{11}$	$2$
$7 \sim 8$		$2000$
$9 \sim 10$		$5 \times 10^4$
$11 \sim 12$		$10^6$	A
$13 \sim 14$			B
$15 \sim 20$

特殊限制 A：对所有 $1 \le i \le \dfrac{\lfloor \sqrt n \rfloor}{3},a_i = 0$

特殊限制 B：对所有 $i \ge 2,a_i = 0$

所有数据满足：$1 \le n \le 10^{11},0 \le k \le 10^6,0 \le a_i < 998244353$