Counting Arrays
Contest: Educational Codeforces Round 138 (Rated for Div. 2)
Difficulty rating: 1900
Tags: combinatorics, dp, math, number theory

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

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

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
2 3

Example output:
6

Example input:
4 2

Example output:
26

Editorial:
We will calculate the answer by subtracting the number of arrays which have only one removal sequence from the total number of arrays. The latter is very simple — it's just $$$m^1 + m^2 + \dots + m^n$$$.
How do we calculate the number of unambiguous arrays? We can always delete the $$$1$$$-st element of an array; so, $$$[1, 1, 1, \dots, 1]$$$ is a removal sequence for each array. So, we have to calculate the number of arrays which have no other removal sequences.
How do we check if the array has no removal sequences other than $$$[1, 1, \dots, 1]$$$? If, at any time, it's possible to remove some element other than the $$$1$$$-st from the array, it creates another removal sequence since we can always complete that sequence.
Let's analyze the constraints on each element of the array. $$$a_1$$$ can be any integer from $$$1$$$ to $$$m$$$. $$$a_2$$$ should be divisible by $$$2$$$ (otherwise, we can remove it on the first step). $$$a_3$$$ should be divisible by $$$3$$$ (otherwise, we can remove it on the first step) and by $$$2$$$ (otherwise, we can remove it on the second step). $$$a_4$$$ should be divisible by $$$2$$$ and $$$3$$$, but not necessarily by $$$4$$$ since an element which is divisible by $$$2$$$ already has a common divisor with $$$4$$$. And so on — using induction, we can show that the $$$i$$$-th element should be divisible by $$$p_1 \cdot p_2 \cdot p_3 \cdot \dots \cdot p_k$$$, where $$$p_1, p_2, \dots, p_k$$$ are all of the primes in $$$[1, i]$$$. Obviously, the number of such elements is $$$\dfrac{m}{p_1 \cdot p_2 \cdot p_3 \cdot \dots \cdot p_k}$$$.
So, we can easily calculate the number of possible elements for each index of the array, and that allows us to count all unambiguous arrays.