P7277 Trivial Bits and Pieces.

A boy sees a book on his desk. He opens it to a certain page. There is only one problem on it.

He writes down a function $f(n)$. It is defined as follows: Let $g(n)$ be the maximum exponent among all prime factors in the prime factorization of $n$. For example, $g(2)=1, g(12)=2$. **Note**: In this problem, assume $g(1)=1$. The samples and testdata have been corrected. Then $f(n) = \max(m-g(n)+1,0) n^k$. Here $m, k$ are parameters given to you. He wants you to compute $$ \sum\limits_{i=1}^n \sum\limits_{j=1}^n f(\gcd(i,j)) $$ and take it modulo $998244353$.

The first line contains three positive integers $n, m, k$.

One line containing one non-negative integer, representing the answer.

For $70\%$ of the testdata, $n \le 10^7$; For $50\%$ of the testdata, $m \le 33$; For $100\%$ of the testdata, $1 \le n \le 10^{10}$, $1 \le m < 998244353$, $1 \le k \le 100$. In addition, one set of hack testdata from @[cqbzljsqwq](/user/154560) is added. Translated by ChatGPT 5