题目背景

zbw 遇上了一道题，由于他急着去找 qby，所以他想让你来帮他做。

题目描述

给你 $n,k$ 求下式的值：

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

其中 $\gcd(i,j)$ 表示 $i,j$ 的最大公约数。

$f$ 函数定义如下：

如果 $k$ 有平方因子 $f(k)=0$，否则 $f(k)=1$。

Update:平方因子定义 如果存在一个整数 $k(k>1),k^2|n$ 则 $k$ 是 $n$ 的一个平方因子

请输出答案对 $998244353$ 取模的值。

输入格式

一行两个整数 $n,k$。

输出格式

一行一个整数，表示答案对 $998244353$ 取模后的值。

3 3

1216

2 6

9714

18 2

260108

143 1

7648044

提示

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^6$，$1 \leq k \leq 10^{18}$。

Update on 2020/3/16:

时间调至 $1$s,卡掉了 $O(n\log k)$,$O(n\log mod)$ 的做法。