题目描述

给定常数 $k$。对于一个长度为 $n$ 的排列 $a$，定义

$$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\}\} $$

对于一个长度为 $n$ 的序列 $a$，定义其权值 $w(a)$ 为 $a$ 中不同的数的个数。

现在，$\text{ducati}$ 想知道，对于所有长度为 $n$ 的排列 $p$，它们的 $w(f(p))$ 之和。

输入格式

一行两个正整数 $n,k$。

输出格式

一行一个整数表示答案。

由于答案可能很大，你需要将它对 $998244353$ 取模。

3 2

10

500000 200000

840847204

提示

【样例解释】

• $p=\{1,2,3\}$，$f(p)=\{2,3\}$，则 $w(f(p))=2$。
• $p=\{1,3,2\}$，$f(p)=\{3,3\}$，则 $w(f(p))=1$。
• $p=\{2,1,3\}$，$f(p)=\{2,3\}$，则 $w(f(p))=2$。
• $p=\{2,3,1\}$，$f(p)=\{3,3\}$，则 $w(f(p))=1$。
• $p=\{3,1,2\}$，$f(p)=\{3,2\}$，则 $w(f(p))=2$。
• $p=\{3,2,1\}$，$f(p)=\{3,2\}$，则 $w(f(p))=2$。

答案为 $2+1+2+1+2+2=10$。

【数据范围】

本题采用捆绑测试。

• 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）：无特殊限制。

对于 $100\%$ 的数据满足，$1 \le k \le n \le 5 \times 10^5$。

【提示】

1. $p$ 是一个长度为 $n$ 的排列，当且仅当每个在 $[1,n]$ 中的整数都在 $p$ 中恰好出现了一次。 例如，$\{1,5,3,2,4\}$ 与 $\{4,2,1,3\}$ 分别是长度为 $5,4$ 的排列，而 $\{1,2,2\}$ 不是长度为 $3$ 的排列，$\{5,4,3,2,1\}$ 不是长度为 $6$ 的排列，$\{1.5,3,1\}$ 不是长度为 $3$ 的排列。

2. 本题并不难。