题目描述

磊神最近在玩“祖玛”。磊神是完美的，他总是追求“伊杆清场”。

在游戏中，给定一个含有不同颜色珠子的序列，你需要发射珠子消除整个序列。当你插入一个珠子，有三个及以上相同颜色的珠子相连接可消去, 消去后若消去处前后有相同颜色的珠子碰撞形成有三个及以上相同颜色的珠子则可继续消去。磊神称只需要插入一个珠子就能全部消除的序列为“完美序列”。

比如一个状如 $1122221$ 的珠子序列，磊神会往 $2222$ 中间发射一个 $2$ ,中间的 $2$ 就会被消除，然后头尾的三个 $1$ 会相互碰撞然后被消除。因此 $1122221$ 是“完美序列”。 $111222$ 则不是“完美序列”，因为消去后任意一侧的珠子，剩余的珠子都不会发生碰撞而消去。

祖玛游戏有 $k$ 种不同的颜色的珠子。他想知道有多少个长度为 $n$ 的“完美序列”，因为答案可能很大，你需要对答案模 $998244353$。

输入描述

第一行有两个正整数 $n, k$，其中 $n$ 表示序列的长度，$k$ 表示颜色的个数。保证 $1 \leqslant n, k \leqslant 10^6$。

输出描述

输出一个整数表示答案对 $998244353$ 取模的结果。

样例

5 2

6

6 3

33

810975 114514

769766223