题目背景

少年看见他的桌上有一本书。
翻开着其中一页。
上面只有一道题。

题目描述

他写下一个函数 $f(n)$。
它是这么定义的：
记 $n$ 的质因子分解式中每个质因子的最大次数为 $g(n)$，例如 $g(2)=1,g(12)=2$。
注意：本题中假设 $g(1)=1$。样例及数据已修正。
则 $f(n) = \max(m-g(n)+1,0) n^k$。
其中 $m,k$ 都是他将给定你的参数。

他希望你求出

$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(\gcd(i,j)) $$

并对 $998244353$ 取模。

输入格式

第一行，三个正整数 $n,m,k$。

输出格式

一行，一个非负整数，表示答案。

4 4 4

1328

6 6 6

410114

10000000000 114514 100

603074925

提示

对于 $70\%$ 的数据，$n \le 10^7$；
对于 $50\%$ 的数据，$m \le 33$；
对于 $100\%$ 的数据，$1 \le n \le 10^{10}$, $1 \le m < 998244353$, $1 \le k \le 100$。

除此之外，添加一组来自