时空限制

1S/512M

题目描述

有 $n$ 个球排成一行。球的颜色有 $k$ 种，分别以数字 $1\sim k$ 表示。

进行 $n-1$ 轮合成，每一轮你选择两个位置相邻的球合成为一个新球，新球的颜色由你从合成前这两个球的颜色中选择。

求有多少种初始情况最终能够合成出颜色为 $1$ 的球，对 $998244353$ 取模。如果两个初始情况中存在某个位置的球颜色不同，视为两个不同的初始情况。

格式

输入格式

第一行包含两个整数 $n,k$，分别表示球的数量和颜色的种类数。

输出格式

输出一个整数表示最终能够合成出颜色为 $1$ 的球的不同初始情况数量。对 $998244353$ 取模。

样例

样例输入 #1

3 2

样例输出 #1

7

样例解释 #1

最终能够合成出颜色为 $1$ 的球的不同初始情况有 $7$ 种：①$\{1,1,1\}$；②$\{1,1,2\}$；③$\{1,2,1\}$；④$\{1,2,2\}$；⑤$\{2,1,1\}$；⑥$\{2,1,2\}$；⑦$\{2,2,1\}$。

样例输入 #2

654321 123456

样例输出 #2

153433298

样例输入 #3

9999999999999999999999999999999999999999 2

样例输出 #3

867663086

数据规模

对于 $20\%$ 的数据，$n\leq 10^6$。

对于 $60\%$ 的数据，$n\leq 10^{18}$。

对于 $100\%$ 的数据，$1\leq n\leq 10^{1000000}$，$2\leq k\leq 10^6$。