CF1749D.Counting Arrays

Consider an array $a$ of length $n$ with elements numbered from $1$ to $n$. It is possible to remove the $i$-th element of $a$ if $gcd(a_i, i) = 1$, where $gcd$ denotes the greatest common divisor. After an element is removed, the elements to the right are shifted to the left by one position.

An array $b$ with $n$ integers such that $1 \le b_i \le n - i + 1$ is a removal sequence for the array $a$ if it is possible to remove all elements of $a$, if you remove the $b_1$-th element, then the $b_2$-th, ..., then the $b_n$-th element. For example, let $a = [42, 314]$:

• $[1, 1]$ is a removal sequence: when you remove the $1$-st element of the array, the condition $gcd(42, 1) = 1$ holds, and the array becomes $[314]$; when you remove the $1$-st element again, the condition $gcd(314, 1) = 1$ holds, and the array becomes empty.
• $[2, 1]$ is not a removal sequence: when you try to remove the $2$-nd element, the condition $gcd(314, 2) = 1$ is false.

An array is ambiguous if it has at least two removal sequences. For example, the array $[1, 2, 5]$ is ambiguous: it has removal sequences $[3, 1, 1]$ and $[1, 2, 1]$. The array $[42, 314]$ is not ambiguous: the only removal sequence it has is $[1, 1]$.

You are given two integers $n$ and $m$. You have to calculate the number of ambiguous arrays $a$ such that the length of $a$ is from $1$ to $n$ and each $a_i$ is an integer from $1$ to $m$.

考虑一个长度为 $n$ 的数组 $a$，其元素编号从 $1$ 到 $n$。当且仅当 $\gcd(a_i, i) = 1$（其中 $\gcd$ 表示最大公约数）时，可以删除 $a$ 的第 $i$ 个元素。删除某个元素后，其右侧的所有元素均向左移动一位。

若存在一个含 $n$ 个整数的数组 $b$，满足对所有 $i$ 均有 $1 \le b_i \le n - i + 1$，且按顺序依次删除 $a$ 的第 $b_1$ 个元素、第 $b_2$ 个元素、……、第 $b_n$ 个元素，最终可将 $a$ 的所有元素全部删除，则称 $b$ 是数组 $a$ 的一个删除序列。例如，设 $a = [42, 314]$：

• $[1, 1]$ 是一个删除序列：首先删除数组中第 $1$ 个元素，此时 $\gcd(42, 1) = 1$ 成立，数组变为 $[314]$；再删除当前数组中第 $1$ 个元素，此时 $\gcd(314, 1) = 1$ 成立，数组变为空。
• $[2, 1]$ 不是一个删除序列：首次尝试删除第 $2$ 个元素时，$\gcd(314, 2) = 1$ 不成立。

若一个数组至少拥有两个不同的删除序列，则称该数组是歧义的（ambiguous）。例如，数组 $[1, 2, 5]$ 是歧义的：它拥有两个删除序列 $[3, 1, 1]$ 和 $[1, 2, 1]$。而数组 $[42, 314]$ 不是歧义的：它唯一的删除序列是 $[1, 1]$。

现给定两个整数 $n$ 和 $m$。你需要计算满足以下条件的歧义数组 $a$ 的个数：$a$ 的长度在 $1$ 到 $n$ 之间（含端点），且每个元素 $a_i$ 均为 $1$ 到 $m$ 之间的整数。

The only line of the input contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5$; $1 \le m \le 10^{12}$).

输入仅包含一行，其中有两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$；$1 \le m \le 10^{12}$）。

Print one integer — the number of ambiguous arrays $a$ such that the length of $a$ is from $1$ to $n$ and each $a_i$ is an integer from $1$ to $m$. Since the answer can be very large, print it modulo $998244353$.

输出一个整数——满足以下条件的模糊数组 $a$ 的个数：数组 $a$ 的长度在 $1$ 到 $n$ 之间，且每个元素 $a_i$ 均为 $1$ 到 $m$ 之间的整数。由于答案可能非常大，请对 $998244353$ 取模后输出。