相邻不同

题目描述

有 $N$ 个人围成一圈,编号为 $1$ 到 $N$。第 $2$ 个人的右侧是第 $1$ 个人,第 $3$ 个人的右侧是第 $2$ 个人,……,第 $N$ 个人的右侧是第 $1$ 个人。

我们要给这 $N$ 个人每人分配一个 $0$ 到 $M-1$ 之间的整数。

在 $M^N$ 种分配方式中,求满足「任意两个相邻的人分到的整数不同」的分配方式的数量,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出:

$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$ 取模。

数据范围

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