UOJ Logo

NOI.AC

1S 512MB

#1598. 气球消消乐

Statistics

问题描述

有 $n$ 只气球,把气球排成一排。初始时,气球都是白色,现在用 $m$ 种颜色给气球涂色,如果相邻的气球的颜色相同,这 $2$ 个气球会发生消消乐,求出会发生消消乐的涂色方法有多少种。最后答案对 $998244353$取模。

输入格式

输入两个整数$n(1 \leq n \leq 10 ^ {12}),m(1 \leq m \leq 10^8)$

输出格式

输出一行表示答案。

样例输入

3 4

样例输出

28