选择题(choice)

题目背景

注意：本场比赛每道题满分均为 100 分，提交显示 Accepted 不一定代表通过。

高中的许多琐碎，终将随着时间的流逝而褪色。可是，小 M 永远记得，那个夏天……

小 M 期中考试由于迷信某些玄学，写挂了。 （你以为呢）

题目描述

期中考试的玄学不灵了，小 M 很伤心，他把一张试卷扔给了你。这张试卷上有 N 道标号从 1 到 N 的单项选择题，每道选择题都有 K 个不同种类选项，且每道题只选择一个选项。

现在小 M 想问你有多少种不同的方案，满足该试卷存在三道或以上标号连续的题目选择同一个选项（例如：第 8，9，10 题都选第 3 种选项，又例如第 3，4，5，6 题都选第 1 种选项）。

本题中，两种方案不同指在这两种方案中，存在至少一道相同标号的题目选择不同种类的选项。答案与 998244353 取模。

一行两个整数 N,K 。

一行一个非负整数，表示符合题目要求的方案数与 998244353 取模后的结果。

样例解释

样例1：有以下几种方案：四题都选同一种，共4种；1，2，3题选同一种，第4题选另一种，共12种；2，3，4题选同一种， 第1题选另一种，共12种。全部加起来有28种。

样例2：符合 AAAAA、AAAAB、BAAAA、AAABB、AAABC、BAAAB、BAAAC、BBAAA、BCAAA 形式的都符合要求。（上述表示中，一种字母代表选择一种答案，字母排列顺序为题号顺序。）

数据范围

对于 10\% 的数据，N \leq 15，K = 4。

对于 50\% 的数据，N \leq 5 \times 10^4，K \leq 15。

另有 20\% 的数据，N \leq 5 \times 10^3。

对于所有数据， 3 \leq N \leq 2 \times 10^5 ， 2 \leq K \leq 10^4 。

其它比赛