A15548 | 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$ .

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}$ ).

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$ .