Child holds a meeting,
Once writes a northern stone.
Dreams stay,
Broken big style.
—— Gong Shifeng, "Spoon, Arsenic"
The little brother handed Lord Divine Tree a copy of "Ah Q Teaches You How to Count". Lord Divine Tree looked at the first problem and found he couldn't do it; Lord Divine Tree looked at the second problem and couldn't even understand the text; ...; Lord Divine Tree looked at the $114514$-th problem and finally solved it in $1919810$ seconds. He decided to include this problem in "Lord Divine Tree Teaches You Math".
For a subsequence $a_{i_1}, a_{i_2}, \dots, a_{i_k}$ of a permutation $\{a_i\}$ of length $n$, if the subsequence satisfies $a_{i_1} > a_{i_2} < a_{i_3} \dots > a_{i_k}$, then this subsequence is called an alternating subsequence. You are required to find the number of permutations of length $n$ such that the longest alternating subsequence has length $K$, modulo $998244353$.
Input
The input consists of a single line containing two integers $n$ and $K$.
Output
Output a single integer representing the answer.
Examples
Input 1
3 2
Output 1
3
Note
The sequences $[1, 3, 2], [2, 3, 1], [3, 2, 1]$ satisfy the requirements.
Input 2
10 6
Output 2
878856
Input 3
5000 1145
Output 3
849619090
Subtasks
Hint: Gong Shifeng, Xiao Wanbang, and the little brother are the same person.
Note: Do not waste too much time on this problem.
| Subtask | Score | $n$ | $K$ |
|---|---|---|---|
| $1$ | $10$ | $\leq 10$ | $\leq n$ |
| $2$ | $20$ | $\leq 5000$ | |
| $3$ | $5$ | $\leq 10^5$ | $=n$ |
| $4$ | $10$ | $\leq n$ | |
| $5$ | $15$ | $\leq 10^9$ | $\leq \min(20,n)$ |
| $6$ | $5$ | $\leq \min(200,n)$ | |
| $7$ | $35$ | $\leq 10^{18}$ | $\leq \min(10^6,n)$ |