题目描述

\(n\)个人住在连续的一排\(n\)个房间里，按顺序编号为\(1 \sim n\)，每个房间只住一个人。他们可能来自\(m\)个不同的国家，一旦相邻的两个房间住着来自 相同 国家的人，他们就会发生争吵，然后爆发可怕的战争。每个人都可能是\(m\)个国家中的任意一个，共有\(m^n\)种可能（有可能这\(n\)个人中并没有某个/某些国家的人）。你想知道，有多少种可能的状态会发生战争。

输入格式

一行，两个正整数\(m,n\)。

输出格式

一个非负整数，爆发战争的状态总数对998244353取模的结果。

样例

输入

2 3

输出

6

样例说明

可能的6种状态分别是：
第一个来自1国家，第二个来自1国家，第三个来自1国家
第一个来自1国家，第二个来自1国家，第三个来自2国家
第一个来自1国家，第二个来自2国家，第三个来自2国家
第一个来自2国家，第二个来自2国家，第三个来自2国家
第一个来自2国家，第二个来自2国家，第三个来自1国家
第一个来自2国家，第二个来自1国家，第三个来自1国家

数据规模、时空限制

对于30%的数据，\(n,m \le 5\)
对于50%的数据，\(n,m \le 10^6\)
对于100%的数据，\(n,m \le 2^{31} - 1\)
时间限制1s，空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人：于剑