Description

Given a constant $k$. For a permutation $a$ of length $n$, define

$$f(a)=\{\max_{1 \le i \le k} \{a_i\},\max_{2 \le i \le k+1} \{a_i\},\cdots,\max_{n-k+1 \le i \le n} \{a_i\}\}$$

For a sequence $a$ of length $n$, define its weight $w(a)$ as the number of distinct values in $a$.

Now, $\text{ducati}$ wants to know, for all permutations $p$ of length $n$, the sum of $w(f(p))$.

Input Format

One line contains two positive integers $n, k$.

Output Format

Output one integer in one line, representing the answer.

Since the answer may be very large, you need to take it modulo $998244353$.

3 2

10

500000 200000

840847204

Hint

[Sample Explanation]

• $p=\{1,2,3\}$, $f(p)=\{2,3\}$, so $w(f(p))=2$.
• $p=\{1,3,2\}$, $f(p)=\{3,3\}$, so $w(f(p))=1$.
• $p=\{2,1,3\}$, $f(p)=\{2,3\}$, so $w(f(p))=2$.
• $p=\{2,3,1\}$, $f(p)=\{3,3\}$, so $w(f(p))=1$.
• $p=\{3,1,2\}$, $f(p)=\{3,2\}$, so $w(f(p))=2$.
• $p=\{3,2,1\}$, $f(p)=\{3,2\}$, so $w(f(p))=2$.

The answer is $2+1+2+1+2+2=10$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (10pts): $n \le 8$.
• Subtask 2 (10pts): $n \le 11$.
• Subtask 3 (30pts): $n \le 100$.
• Subtask 4 (20pts): $n \le 400$.
• Subtask 5 (20pts): $n \le 4000$.
• Subtask 6 (10pts): no special constraints.

For $100\%$ of the data, $1 \le k \le n \le 5 \times 10^5$.

[Notes]

1. $p$ is a permutation of length $n$ if and only if every integer in $[1,n]$ appears in $p$ exactly once.
   For example, $\{1,5,3,2,4\}$ and $\{4,2,1,3\}$ are permutations of length $5$ and $4$, respectively, while $\{1,2,2\}$ is not a permutation of length $3$, $\{5,4,3,2,1\}$ is not a permutation of length $6$, and $\{1.5,3,1\}$ is not a permutation of length $3$.

2. This problem is not difficult.

Translated by ChatGPT 5