在表格里造序列

题目限制

3000 ms 128 M

题目描述

他有一张 $n \times n$ 的表格，行和列都以 $1\sim n$ 编号。

在第 $i$ 行第 $j$ 列的格子里，他造了许许多多的序列。

这些序列是满足以下要求的所有序列：

1. 序列长度为给定的正整数 $m$；

2. 序列中元素均为 $[1,n]$ 内的整数；

3. 序列中元素的最大公约数和 $i,j$ 的最大公约数相等。

他突然发现这些序列有好多好多，所以他想具体数一数。

他希望你能帮他数出所有格子里的序列个数之和。

以及，他知道这很困难，所以希望你能将答案对 $998244353$ 取模。

输入格式

一行输入两个正整数 n, m。（1≤n≤1e9,1≤m≤1e18）

输出格式

一行输出一个非负整数，表示答案。

数据范围

对于 $20\%$ 的数据，$n, m \le 10$；

对于 $50\%$ 的数据，$n, m \le 10^5$；

对于 $70\%$ 的数据，$n \le 10^7$；

对于 $100\%$ 的数据，$1 \le n \le 10^9, 1 \le m \le 10^{18}$。

输入样例

样例 #1：
2 2

样例 #2：
3 3

输出样例

样例 #1：
10

样例 #2：
177

样例解释

对于样例 #1，显然可知在 $(1,1),(1,2),(2,1)$ 内的序列各有 $3$ 个，在 $(2,2)$ 内的序列仅有 $1$ 个，故答案为 $3 + 3 + 3 + 1 \equiv 10 \pmod{998244353}$。