{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$P'_1$ $P'_2$ $\\cdots$ $P'_N$"},{"iden":"sample input 1","content":"3 1\n3 1 2"},{"iden":"sample output 1","content":"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'$."},{"iden":"sample input 2","content":"4 3\n4 3 2 1"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"5 2\n4 2 1 5 3"},{"iden":"sample output 3","content":"3"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}