{"problem":{"name":"[ICPC 2020 Shanghai R] The Journey of Geor Autumn","description":{"content":"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 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9823"},"statements":[{"statement_type":"Markdown","content":"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.\n\nGeor 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 $\\textit{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}$.\n\nHelp Geor calculate how many good poems there are, given $n$ and $k$. To avoid huge numbers, output the answer modulo $998244353$.\n\n## Input\n\nThe 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$).\n\n## Output\n\nOutput only one integer in one line---the number of good poems modulo $998244353$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9823","tags":["动态规划 DP","2020","上海","O2优化","组合数学","逆元","ICPC"],"sample_group":[["1 1","1"],["2 3","2"],["3 2","4"],["4 2","10"]],"created_at":"2026-03-03 11:09:25"}}