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

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

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


-----Examples-----

Input
2 3
Output
6
Input
4 2
Output
26
Input
4 6
Output
1494
Input
1337 424242424242
Output
119112628


-----Note-----

None

Difficulty: HARD
Tags: Number theory

Combinatorics

Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
(n, m) = map(int, input().split())
if m == 1:
	print(n - 1)
	exit()
M = 998244353
tot = (pow(m, n + 1, M) - 1) * pow(m - 1, -1, M) - 1
p = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])
fac = [1, 1]
for i in range(2, 37):
	fac += (fac[-1] * (i if i in p else 1),)
(i, res, temp) = (2, m, m)
while i <= min(n, 36) and fac[i] <= m:
	temp = m // fac[i] * temp % M
	res = (res + temp) % M
	i += 1
print((tot - res) % M)


from typing import List
from math import sqrt
MOD = 998244353

def sieve(n) -> List[bool]:
	is_prime = [True] * (n + 1)
	is_prime[0] = is_prime[1] = False
	for i in range(4, n + 1, 2):
		is_prime[i] = False
	for i in range(3, int(sqrt(n)) + 2, 2):
		if is_prime[i]:
			for j in range(i * i, n, 2 * i):
				is_prime[j] = False
	return is_prime

def main():
	(n, m) = map(int, input().split())
	is_prime = sieve(n)
	unambiguous = 0
	last = 1
	primes_acc = 1
	for i in range(1, n + 1):
		if primes_acc > m:
			break
		if is_prime[i]:
			primes_acc *= i
		last *= m // primes_acc
		unambiguous = (unambiguous + last) % MOD
	if m != 1:
		all = pow(m, n + 1, MOD) - 1
		all = (all * pow(m - 1, MOD - 2, MOD) - 1 + MOD) % MOD
	else:
		all = n % MOD
	ans = (all - unambiguous + MOD) % MOD
	print(ans)
main()


def GCD(x, y):
	if x < y:
		(x, y) = (y, x)
	while y != 0:
		temp = x % y
		x = y
		y = temp
	return x
(n, m) = [int(x) for x in input().split(' ')]
pri = [0, 1, 2]
for i in range(3, 60):
	if GCD(pri[-1], i) == 1 and i < 60:
		pri.append(pri[-1] * i)
	else:
		pri.append(pri[-1])
ans = 0
now = 1
for i in range(n):
	now = now * m % 998244353
	ans += now
ans -= m
for i in range(2, n + 1):
	if i <= 50:
		tem = 1
		for j in range(1, i + 1):
			tem = tem * (m // pri[j]) % 998244353
		ans -= tem
print(ans % 998244353)


import math
(n, m) = input().split()
n = int(n)
m = int(m)
mod = 998244353
ans = 0
mul = m % mod
for i in range(1, n + 1):
	ans += mul
	if ans >= mod:
		ans -= mod
	mul = mul * m % mod
factor = 1
mul = 1
for i in range(1, n + 1):
	if math.gcd(factor, i) == 1:
		factor *= i
	cnt = int(m / factor)
	if cnt == 0:
		break
	mul = mul * cnt % mod
	ans -= mul
	if ans < 0:
		ans += mod
print(ans)


(n, m) = map(int, input().split())
mod = 998244353
num = n
prime = [True for i in range(num + 1)]
p = 2
while p * p <= num:
	if prime[p] == True:
		for i in range(p * p, num + 1, p):
			prime[i] = False
	p += 1
final = 0
total = 1
nonamb = 1
totpripro = 1
flag = n + 1
for i in range(1, n + 1):
	if prime[i]:
		totpripro *= i
		if totpripro > m:
			flag = i
			break
	total *= m
	total %= mod
	nonamb *= m // totpripro
	final += total - nonamb
	final %= mod
for i in range(flag, n + 1):
	total *= m
	total %= mod
	final += total
	final %= mod
print(final)


mod = 998244353
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
v = [1] * 38
for prime in primes:
	for i in range(prime, 38):
		v[i] *= prime
(n, m) = map(int, input().split())
ans = 0
ac = 1
for i in range(1, n + 1):
	ac *= m
	ac %= mod
	uc = 1
	if i >= 38:
		uc = 0
	else:
		for k in range(1, i + 1):
			if v[k] > m:
				uc = 0
				break
			cc = m // v[k]
			uc *= cc
			uc %= mod
	tc = ac - uc + mod
	ans += tc
	ans %= mod
print(ans)


N = 3 * 10 ** 5 + 5
(n, m) = map(int, input().split())
p = [1 for i in range(N)]
mod = 998244353
for i in range(2, N):
	if p[i] == 1:
		for j in range(2 * i, N, i):
			p[j] = 0
ans = m
curr = m
l = 1
for i in range(2, n + 1):
	if p[i] == 1:
		l = l * i
	if l > m:
		break
	curr = curr * (m // l) % mod
	ans = (ans + curr) % mod
t = m
curr = m
for i in range(2, n + 1):
	curr = curr * m % mod
	t = (t + curr) % mod
ans = (t - ans + mod) % mod
print(ans)


from math import gcd
(n, m) = map(int, input().split())
SUM = 0
sum = m
L = 2
k = m ** 2
for i in range(2, n + 1):
	if gcd(i, L) == 1 and L <= 10 ** 12:
		L *= i
	sum *= m // L
	sum = sum % 998244353
	SUM += k - sum
	k *= m
	k = k % 998244353
print(SUM % 998244353)


from math import gcd
(n, m) = map(int, input().split())
ans = 0
cur = m
g = 2
q = m * m
for i in range(2, n + 1):
	if gcd(g, i) == 1 and g < 10 ** 13:
		g *= i
	cur *= m // g
	cur = cur % 998244353
	ans += q - cur
	q *= m
	q = q % 998244353
	ans = ans % 998244353
print(ans % 998244353)


import math
module = 998244353

def is_prime(n):
	if n == 1:
		return True
	for x in range(2, int(math.sqrt(n)) + 1):
		if n % x == 0:
			return False
	return True
line1 = input().split(' ')
n = int(line1[0])
m = int(line1[1])
s = m
ans = 0
productP = 1
F = 0
for i in range(2, n + 1):
	if productP <= m and is_prime(i):
		productP *= i
	tmp = m * F % module
	x = m - int(m / productP)
	tmp += (s - F) * x % module
	tmp %= module
	F = tmp
	ans = (F + ans) % module
	s = s * m % module
print(ans)


sz = 300010
stat = [1 for i in range(sz)]
stat[0] = 0
stat[1] = 0
for i in range(2, sz):
	if stat[i] == 1:
		for j in range(i * i, sz, i):
			stat[j] = 0
(n, m) = list(map(int, input().split()))
mod = 998244353
p = 1
l = 1
ans = 0
flag = 0
m1 = 1
for i in range(1, n + 1):
	if stat[i] == 1 and flag == 0:
		l *= i
	if m // l == 0:
		flag = 1
	if flag == 1:
		p = 0
	p = p * (m // l)
	p = p % mod
	m1 *= m
	m1 = m1 % mod
	ans += m1 - p
	ans = ans % mod
print(ans)


import math

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
lists = input().split()
number_element_max = int(lists[0])
maximum_value_of_element = int(lists[1])
nb_normal = maximum_value_of_element
increment = 1
res = 0
for i in range(2, number_element_max + 1):
	if nb_normal != 0 and isPrime(i):
		increment *= i
	number_possibility = maximum_value_of_element // increment
	res += pow(maximum_value_of_element, i, 998244353)
	nb_normal *= number_possibility
	nb_normal = nb_normal % 998244353
	res -= nb_normal
print(res % 998244353)


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	mo = 998244353
	isPrime = [True] * 40
	for i in range(2, 40):
		if isPrime[i]:
			for j in range(2 * i, 40, i):
				isPrime[j] = False
	ans = 0
	others = m
	val = 1
	j = 2
	for i in range(2, n + 1):
		while j <= i and val <= m and (j < 40):
			if isPrime[j]:
				val *= j
			j += 1
		if val > m:
			ans += pow(m, i, mo)
			ans %= mo
			continue
		others *= m // val
		others %= mo
		ans += (pow(m, i, mo) - others) % mo
	return ans
print(solve())


def add(a, b, mod):
	return (a + b) % mod

def mul(a, b, mod):
	return a * b % mod

def sub(a, b, mod):
	return (a - b + mod) % mod

def binpow(a, n, mod):
	if n == 0:
		return 1
	if n % 2 == 1:
		return mul(a, binpow(a, n - 1, mod), mod)
	b = binpow(a, n // 2, mod)
	return mul(b, b, mod)

def prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return n > 1
MOD = 998244353
(n, m) = map(int, input().split())
p = 1
ans = 0
cur = m
ans = sub(ans, cur, MOD)
for i in range(1, n + 1):
	ans = add(ans, int(pow(m, i, MOD)), MOD)
for i in range(1, n):
	if prime(i + 1):
		p *= i + 1
	if p > m:
		break
	cur = mul(cur, m // p, MOD)
	ans = sub(ans, cur, MOD)
print(ans)


import math
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

def sw(n, m):
	g = 1
	for i in prime:
		if i <= n:
			g *= i
	return m // g

def wronganswer(n, m):
	ans = 1
	if n <= 37:
		for i in range(1, n + 1):
			ans = ans * sw(i, m) % 998244353
		return ans
	else:
		return 0

def rightanswer(n, m):
	return pow(m, n, 998244353) - wronganswer(n, m) % 998244353
(n, m) = map(int, input().split())
sum = 0
if n == 1:
	print(0)
else:
	for i in range(2, n + 1):
		sum += rightanswer(i, m)
		sum %= 998244353
	print(sum)


(n, m) = [int(i) for i in input().split()]
prime = [1] * (n + 1)
prime[1] = 0
for i in range(2, n + 1):
	if prime[i]:
		for j in range(i * i, n + 1, i):
			prime[j] = 0
prod = 1
cur = 1
ans = 0
all_cnt = 0
MOD = 998244353
for i in range(1, n + 1):
	if prime[i] and prod <= m:
		prod = prod * i
	cur = cur * (m // prod) % MOD
	ans = (ans + cur) % MOD
	all_cnt = (all_cnt + pow(m, i, MOD)) % MOD
print((all_cnt - ans) % MOD)


mod = 998244353

def solve(n, m):
	primes = [1] * (n + 1)
	for i in range(2, n + 1):
		for j in range(i + i, n + 1, i):
			primes[j] = 0
	cur = 1
	ans = 0
	b = m
	for i in range(1, n + 1):
		if primes[i]:
			b //= i
		cur = cur * b % mod
		ans = (ans + pow(m, i, mod) - cur) % mod
	return ans

def main():
	(n, m) = list(map(int, input().split()))
	print(solve(n, m))
main()