{"problem":{"name":"Roughly Sorted","description":{"content":"Snuke received a permutation $P=(P_1,P_2,\\cdots,P_N)$ of $(1,\\ 2,\\ ...\\ N)$ and an integer $K$. He did some number of swaps of two adjacent elements in $P$ so that the following condition would be sat","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc054_c"},"statements":[{"statement_type":"Markdown","content":"Snuke received a permutation $P=(P_1,P_2,\\cdots,P_N)$ of $(1,\\ 2,\\ ...\\ N)$ and an integer $K$. He did some number of swaps of two adjacent elements in $P$ so that the following condition would be satisfied.\n\n*   For each $1 \\leq i \\leq N$, there are at most $K$ indices $j$ such that $1 \\leq j< i$ and $P_j>P_i$.\n\nHere, he did the **minimum** number of swaps needed to achieve this condition.\nAfterward, he has forgotten the original permutation he received. Given the permutation $P'$ after the swaps, find the number, modulo $998244353$, of permutations that the original permutation $P$ could be.\n\n## Constraints\n\n*   $2 \\leq N \\leq 5000$\n*   $1 \\leq K \\leq N-1$\n*   $1 \\leq P'_i \\leq N$\n*   $P'_i \\neq P'_j$ ($i \\neq j$)\n*   For each $1 \\leq i \\leq N$, there is at most $K$ indices $j$ such that $1 \\leq j< i$ and $P'_j>P'_i$.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$P'_1$ $P'_2$ $\\cdots$ $P'_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc054_c","tags":[],"sample_group":[["3 1\n3 1 2","2\n\n$P$ could be one of the following two permutations.\n\n*   $P=(3,1,2)$: The minimum number of swaps needed is $0$. After zero swaps, the permutation is equal to $P'$.\n*   $P=(3,2,1)$: The minimum number of swaps needed is $1$: swapping $P_2$ and $P_3$ results in $P=(3,1,2)$, which satisfies the condition and is equal to $P'$."],["4 3\n4 3 2 1","1"],["5 2\n4 2 1 5 3","3"]],"created_at":"2026-03-03 11:01:14"}}