Description

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$.

Input Format

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

Output Format

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

4 4 4

1328

6 6 6

410114

10000000000 114514 100

603074925

Hint

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

Translated by ChatGPT 5