AT_abc307_e [ABC307E] Distinct Adjacent

题目描述

有 $N$ 个人，编号从 $1$ 到 $N$，他们围成一圈站立。$1$ 号的右边是 $2$ 号，$2$ 号的右边是 $3$ 号，……，$N$ 号的右边是 $1$ 号。

现在要给每个人各发一个整数，这个整数在 $0$ 以上且小于 $M$。
在所有 $M^N$ 种分发方式中，问有多少种分发方式满足任意相邻的两个人所分得的数都不相同？请输出这个数对 $998244353$ 取模的结果。

输入格式

输入从标准输入中给出，格式如下：

$N$ $M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 3

输出 #1

6

输入输出样例 #2

输入 #2

4 2

输出 #2

2

输入输出样例 #3

输入 #3

987654 456789

输出 #3

778634319

说明/提示

限制条件

• $2 \leq N, M \leq 10^6$
• $N, M$ 均为整数

样例解释 1

当分给 $1,2,3$ 号人的整数分别为 $(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)$ 时，共有 $6$ 种方式。

样例解释 2

当分给 $1,2,3,4$ 号人的整数分别为 $(0,1,0,1),(1,0,1,0)$ 时，共有 $2$ 种方式。

样例解释 3

请输出对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译