Sum of Special GCD Function

Given three positive integers n, m, and k, define a function ( f(n) ) as follows. First, for any positive integer ( n ), let ( g(n) ) be the maximum exponent among the primes in the prime factorization of ( n ). In particular, we assume ( g(1)=1 ). For example, since ( 12=2^2\cdot3^1 ), we have ( g(12)=2 ), and ( g(2)=1 ). Then [ f(n)=\max\Big(m-g(n)+1,0\Big)\cdot n^k, ] where ( n^k ) denotes ( n ) raised to the power ( k ) and both m and k are given parameters.

Your task is to compute [ S=\sum_{i=1}^{n}\sum_{j=1}^{n} f(\gcd(i,j)) \mod 998244353, ] where ( \gcd(i,j) ) denotes the greatest common divisor of ( i ) and ( j ).

inputFormat

The input consists of a single line containing three space-separated integers: n, m, and k.

outputFormat

Output a single integer, which is the value of S modulo 998244353.

sample

1 1 1

1