407849: GYM102900 E The Journey of Geor Autumn
Description
Once upon a time, there was a witch named Geor Autumn, who set off on a journey across the world. Along the way, she would meet all kinds of people, from a country full of ICPC competitors to a horse in love with dota—but with each meeting, Geor would become a small part of their story, and her own world would get a little bit bigger.
Geor just arrived at the state of Shu where people love poems. A poem is a permutation $$$(a_1,\ldots, a_n)$$$ of $$$[n]$$$. ($$$(a_1,\ldots, a_n)$$$ is a permutation of $$$[n]$$$ means that each $$$a_i$$$ is an integer in $$$[1,n]$$$ and that $$$a_1,\ldots, a_n$$$ are distinct.) One poem is good if for all integer $$$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 there are, given $$$n$$$ and $$$k$$$. To avoid huge numbers, output the answer modulo $$$998244353$$$.
InputThe 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$$$).
OutputOutput only one integer in one line—the number of good poems modulo $$$998244353$$$.
ExamplesInput1 1Output
1Input
2 3Output
2Input
3 2Output
4Input
4 2Output
10