P5915 冬至

>春生秋死，不知冬至。

给你 $1 \sim k$ 的整数，你可以选其中的数，组成长度为 $n$ 的串（可重复使用），且不能有子串是 $1\sim k$ 的排列。 问方案总数模 $998244353$。

一行两个正整数 $n,k$。

一行一个整数，表示方案总数模 $998244353$ 的值。

【样例 1 解释】 可以组成的合法排列有：$1,1,1$ 和 $2,2,2$ 其余均不合法，都含有 $1 \sim 2$ 的排列，因此答案为 $2$。 【样例 2 解释】 总共有 $7^7$ 种情况，其中有 $7!$ 个不合法（即 $1 \sim 7$ 的排列情况数），答案为 $7^7-7!$，即 $818503$。 【数据范围】 对于 $100\%$ 的数据，$1\le k \le 10^4$，$1\le n \le 10^9$。 By：毕克