Problem Background

A young man notices a book on his desk.
It is open to a certain page.
On that page, there is only one problem.

Problem Description

He writes a function \( f(n) \).
It is defined as follows:
Let \( g(n) \) be the maximum exponent of the prime factors in the prime factorization of \( n \), for example, \( g(2)=1, g(12)=2 \).
Note: In this problem, it is assumed that \( g(1)=1 \). The examples and data have been corrected.
Then \( f(n) = \max(m-g(n)+1,0) n^k \).
Where \( m \) and \( k \) are parameters he will provide to you.

He wants you to calculate
$$ \sum\limits_{i=1}^n \sum\limits_{j=1}^n f(\gcd(i,j)) $$

and take the result modulo \( 998244353 \).

Input Format

The first line contains three positive integers \( n, m, k \).

Output Format

A single line containing a non-negative integer, representing the answer.

Sample Input and Output

Sample Input #1

4 4 4

Sample Output #1

1328

Sample Input #2

6 6 6

Sample Output #2

410114

Sample Input #3

10000000000 114514 100

Sample Output #3

603074925

Notes

For 70% of the data, \( n \le 10^7 \);
For 50% of the data, \( m \le 33 \);
For 100% of the data, \( 1 \le n \le 10^{10} \), \( 1 \le m < 998244353 \), \( 1 \le k \le 100 \).

Additionally, a set of hack data from @cqbzljsqwq has been added.

见题面 Input 部分

见题面 Output 部分