P5915 Winter Solstice

> Spring is born and autumn dies, not knowing the Winter Solstice.

You are given the integers $1 \sim k$. You may choose numbers from them to form a string of length $n$ (repetition is allowed), and no substring is allowed to be a permutation of $1 \sim k$. Find the total number of valid strings modulo $998244353$.

A single line with two positive integers $n, k$.

A single line with one integer, the total number of valid strings modulo $998244353$.

[Sample 1 Explanation] The valid strings that can be formed are: $1,1,1$ and $2,2,2$. All others are invalid, because they contain a permutation of $1 \sim 2$. Therefore, the answer is $2$. [Sample 2 Explanation] There are $7^7$ strings in total. Among them, $7!$ are invalid (i.e. the number of permutations of $1 \sim 7$). So the answer is $7^7-7!$, which is $818503$. [Constraints] For all testdata, $1\le k \le 10^4$, $1\le n \le 10^9$. By: Bike (毕克). Translated by ChatGPT 5