题目背景
zbw 遇上了一道题，由于他急着去找 qby，所以他想让你来帮他做。
题目描述
给你$n,k$求下式的值：
$sumlimits_{i=1}^nsumlimits_{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$取模后的值。
输入输出样例
输入样例 #1
3 3输出样例 #1
1216输入样例 #2
2 6输出样例 #2
9714输入样例 #3
18 2输出样例 #3
260108输入样例 #4
143 1输出样例 #4
7648044说明/提示
| 测试点 | $n$ | $k$ |
|---|---|---|
| $1,2$ | $\leq 10^3$ | $\leq10^3$ |
| $3,4$ | $\leq 2 \times 10^3$ | $\leq10^{18}$ |
| $5 sim8$ | $\leq 5 \times 10^4$ | $\leq10^{18}$ |
| $9$ | $\leq 5 \times10^6$ | $=1$ |
| $10,11$ | $\leq 5 \times10^6$ | $=2$ |
| $12,13$ | $\leq 5 \times10^6$ | $\leq10^3$ |
| $14 sim20$ | $\leq 5 \times10^6$ | $\leq10^{18}$ |
对于$100\%$的数据，$1 leq n leq 5 imes 10^6$，$1 leq k leq 10^{18}$。
Update on 2020/3/16:
时间调至$1$s,卡掉了$O(nlog k)$,$O(nlog mod)$的做法。