简单题
题目背景
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$ 取模后的值。
输入输出样例
输入样例 #1
3 3输出样例 #1
1216输入样例 #2
2 6输出样例 #2
9714输入样例 #3
18 2输出样例 #3
260108输入样例 #4
143 1输出样例 #4
7648044说明
| 测试点|$n$ |$k$ |
| :----------: | :----------: | :----------: |
| $1,2$ |$\leq10^3$ |$\leq10^3$ |
| $3,4$ |$\leq2 \times 10^3$ |$\leq10^{18}$ |
| $5 \sim8$ | $\leq5 \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 \times 10^6$，$1 \leq k \leq 10^{18}$。
**Update on 2020/3/16:**
时间调至 $1$s,卡掉了 $O(n\log k)$,$O(n\log mod)$ 的做法。