当前没有测试数据。

E - 不同的相邻

得分：$475$ 分

问题描述

有 $N$ 个人围成一个圆圈，编号从 $1$ 到 $N$。第 $1$ 个人在第 $2$ 个人的右边，第 $2$ 个人在第 $3$ 个人的右边，...，第 $N$ 个人在第 $1$ 个人的右边。

我们给这 $N$ 个人中的每个人分配一个介于 $0$ 和 $M-1$ 之间的整数。
在 $M^N$ 种分配整数的方法中，找到满足相邻的两个人没有相同整数的方法的数量。答案对 $998244353$ 取模。

约束

• $2 \leq N,M \leq 10^6$
• $N$ 和 $M$ 是整数。

输入

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

$N$ $M$

输出

输出答案。

3 3

6

有六种满足要求的方法，其中分配给人 $1,2,3$ 的整数是 $(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)$。

4 2

2

有两种满足要求的方法，其中分配给人 $1,2,3,4$ 的整数是 $(0,1,0,1),(1,0,1,0)$。

987654 456789

778634319

一定要求答案对 $998244353$ 取模。