Type: Default 1000ms 256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

有两个正整数 nnmm

我们考虑所有长度为 nn,每个元素在 [1,m][1,m] 的整数序列。对于所有整数序列,设 lcmlcm 为这个序列中元素的最小公倍数,gcdgcd 为这个序列中元素的最大公约数,我们希望求出 lcmgcdlcm^{gcd}。你需要对于所有这些整数序列,计算 lcmgcdlcm^{gcd} 之积 mod 998244353mod \ 998244353

即,我们需要计算:

$$\left ( \prod_{x_1,x_2,\cdots,x_n\in[1,m]} lcm(x_1,x_2,\cdots,x_n)^{gcd(x_1,x_2,\cdots,x_n)} \right) mod \ 998244353 $$

输入格式

一行两个正整数 n,mn,m

输出格式

输出一行一个整数,表示答案。

1 3
108

数据范围

对于所有数据,n108,m200000n\leq 10^8,m\leq 200000

子任务 1(10 分):n,m5n,m\leq 5

子任务 2(20 分):n,m50n,m\leq 50

子任务 3(10 分):n,m500n,m\leq 500

子任务 4(20 分):n,m50000n,m\leq 50000

子任务 5(20 分):n,m200000n,m\leq 200000

子任务 6(20 分):无特殊限制。

虚假的比赛

Not Attended
Status
Done
Rule
IOI
Problem
4
Start at
2023-10-6 8:00
End at
2023-10-7 8:00
Duration
24 hour(s)
Host
Partic.
56