Background

zbw ran into a problem. Since he is in a hurry to meet qby, he wants you to solve it for him.

Problem Description

Given $n, k$, find the value of the following expression:

$\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k f(\gcd(i,j)) \gcd(i,j)$

Here, $\gcd(i,j)$ denotes the greatest common divisor of $i$ and $j$.

The function $f$ is defined as follows:

If $k$ has a square factor, then $f(k)=0$; otherwise, $f(k)=1$.

Update: Definition of a square factor. If there exists an integer $k(k>1)$ such that $k^2 \mid n$, then $k$ is a square factor of $n$.

Output the answer modulo $998244353$.

Input Format

One line containing two integers $n, k$.

Output Format

One line containing one integer, meaning the value of the answer modulo $998244353$.

3 3

1216

2 6

9714

18 2

260108

143 1

7648044

Hint

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^6$, $1 \leq k \leq 10^{18}$.

Update on 2020/3/16:

The time limit was changed to $1$s, ruling out solutions of $O(n\log k)$ and $O(n\log mod)$.

Translated by ChatGPT 5