题目描述

给定一个长度为 $n$ 的环，每个位置可以填 $1\sim m$，求有多少种方案，满足相邻位置颜色不相同，对 $998244353$ 取模。

输入格式

第一行输入 $N$ $M$

输出格式

输出一个整数代表方案数。

3 3

6

4 2

2

987654 456789

778634319

提示

数据范围

• $2\ \leq\ N,M\ \leq\ 10^6$

样例 1 解释

$6$ 种方案分别是 $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$