Problem Background

Born in spring, die in autumn, unaware of the winter solstice.

Problem Description

Given integers from $1$ to $k$, you can select numbers to form a sequence of length $n$ (numbers can be reused), with the condition that no subsequence is a permutation of $1$ to $k$.

Calculate the total number of such sequences modulo $998244353$.

Input Format

A single line containing two positive integers $n$ and $k$.

Output Format

A single integer representing the total number of valid sequences modulo $998244353$.

Sample Input and Output

Sample Input #1

3 2

Sample Output #1

2

Sample Input #2

7 7

Sample Output #2

818503

Sample Input #3

114514 233

Sample Output #3

782307368

Notes

Sample 1 Explanation:
Valid sequences include: $1,1,1$ and $2,2,2$.
All other sequences are invalid as they contain a permutation of $1$ to $2$, hence the answer is $2$.

Sample 2 Explanation:
There are a total of $7^7$ possible sequences, of which $7!$ are invalid (i.e., permutations of $1$ to $7$). The answer is $7^7 - 7!$, which equals $818503$.

Data Range:
For $100\%$ of the data, $1 \le k \le 10^4$, $1 \le n \le 10^9$.

By: Bi Ke

见题面 Input 部分

见题面 Output 部分