AT_arc232_d.Delete Different

You are given integers $N$ and $K$.

For an integer sequence $S$ consisting of integers between $1$ and $K$, inclusive, define its score $f(S)$ as follows.

• Repeat the following operation until all elements of $S$ are equal. The number of times this operation is performed is $f(S)$.

  • Let $|S|$ be the length of $S$ before the operation. For every $i$ satisfying $2 \leq i \leq |S|$ and $S_{i-1} \ne S_i$, simultaneously delete the $i$-th element of $S$. Concatenate the remaining elements in their original order to form the new $S$.

There are $K^N$ integer sequences $S$ of length $N$ consisting of integers between $1$ and $K$, inclusive. Find the sum of $f(S)$ over all of them, modulo $998244353$.

给你整数 $N$ 和 $K$。

对于一个由 $1$ 到 $K$（含）之间的整数组成的整数序列 $S$，定义其得分 $f(S)$ 如下：

• 重复执行以下操作，直到 $S$ 中所有元素均相等。该操作执行的次数即为 $f(S)$。

  • 设操作前 $S$ 的长度为 $|S|$。对每个满足 $2 \leq i \leq |S|$ 且 $S_{i-1} \ne S_i$ 的下标 $i$，同时删除 $S$ 的第 $i$ 个元素。将剩余元素按原顺序拼接，得到新的 $S$。

共有 $K^N$ 个长度为 $N$、且每个元素均在 $1$ 到 $K$（含）之间的整数序列 $S$。求所有这些序列的 $f(S)$ 之和，并对 $998244353$ 取模。

The input is given from Standard Input in the following format:

$N$ $K$

输入从标准输入中以如下格式给出：

$N$ $K$

Output the answer.

输出答案。

Sample 1 Explanation:
The scores of $(1,1,1)$ and $(2,2,2)$ are $0$, and the scores of $(1,2,2)$ and $(2,1,1)$ are $2$. The scores of the other four sequences are $1$, so the sum is $8$.

Sample 2 Explanation:
For example, $S=(1,2,2,2,1,2)$ changes as follows, so its score is $3$.

$(1,2,2,2,1,2) \to (1,2,2) \to (1,2) \to (1)$

Constraints

• $2 \leq N \leq 100$
• $2 \leq K < 998244353$
• All input values are integers.

样例 1 解释：
序列 $(1,1,1)$ 和 $(2,2,2)$ 的得分为 $0$，序列 $(1,2,2)$ 和 $(2,1,1)$ 的得分为 $2$。其余四个序列的得分均为 $1$，因此总和为 $8$。

样例 2 解释：
例如，序列 $S=(1,2,2,2,1,2)$ 按如下方式变化，故其得分为 $3$。

$(1,2,2,2,1,2) \to (1,2,2) \to (1,2) \to (1)$

约束条件

• $2 \leq N \leq 100$
• $2 \leq K < 998244353$
• 所有输入值均为整数。