P7277 平凡点滴

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

他写下一个函数 $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$。

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

对于 $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$。 除此之外，添加一组来自 @[cqbzljsqwq](/user/154560) 的 Hack 数据。