题目描述

$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提高组集训
供题人：于剑