Background

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

Problem Description

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$.

Input Format

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

Output Format

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

3 2

2

7 7

818503

114514 233

782307368

Hint

[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