Problem Description

Problem Summary

Given integers \(1 \le k \le n\), a permutation of \(1 \sim n\) is considered a "good permutation" if it satisfies the following property:

\[ \forall k < i \le n, ~ a_i > \min(a_{i-k}, a_{i-k+1}, \ldots, a_{i-1}) \]

Calculate the number of good permutations modulo \(998244353\).

Input Format

A single line containing two integers \(n\) and \(k\).

Output Format

A single line containing the number of good permutations modulo \(998244353\).

Detailed Description

Once upon a time, there was a witch named Geor Autumn, who embarked on a journey across the world. Along the way, she encountered various individuals, from a country full of ICPC competitors to a horse in love with dota. With each encounter, Geor became a small part of their story, and her own world expanded a little bit more.

Geor has just arrived in the state of Shu, where people are fond of poems. A poem is a permutation \((a_1, \ldots, a_n)\) of \([n]\). A poem is considered "good" if for all integers \(i\) satisfying \(i > k\) and \(i \le n\), \(a_i > \min(a_{i-k}, \ldots, a_{i-1})\). Here, \(\min(a_{i-k}, \ldots, a_{i-1})\) denotes the minimum value among \(a_{i-k}, \ldots, a_{i-1}\).

Help Geor calculate how many good poems exist given \(n\) and \(k\). To avoid dealing with extremely large numbers, output the answer modulo \(998244353\).

Input and Output Format

Input Format

The first line contains two integers \(n\) and \(k\) separated by a single space (\(1 \le n \le 10^7\), \(1 \le k \le 10^7\)).

Output Format

Output a single integer in one line, which is the number of good poems modulo \(998244353\).

Sample Input and Output

Sample Input #1

1 1

Sample Output #1

1

Sample Input #2

2 3

Sample Output #2

2

Sample Input #3

3 2

Sample Output #3

4

Sample Input #4

4 2

Sample Output #4

10

见题面 Input 部分

见题面 Output 部分