{"raw_statement":[{"iden":"problem statement","content":"You are given positive integers $N$ and $K$, and a sequence of $N$ positive integers: $A=(A_{1},A_{2},\\dots,A_{N})$.\nFor a permutation $P=(P_{1},P_{2},\\dots,P_{N})$ of $(1,2,\\dots,N)$, consider the following problem \"MST on Line,\" and let $f(P)$ the answer.\n\n> **Problem: MST on Line**\n> We have a weighted undirected graph $G$ with $N$ vertices numbered $1$ to $N$. For every integer pair $(i,j)$ such that $1\\leq i\\lt j\\leq N$, the following holds for $G$.\n> \n> *   If $j-i\\leq K$, there is an edge between vertex $i$ and vertex $j$, whose weight is **$\\max(A_{P_{i}},A_{P_{j}})$**.\n> *   If $j-i\\gt K$, there is no edge between vertex $i$ and vertex $j$.\n> \n> Find the total weight of the edges of a minimum spanning tree of $G$.\n\nFind the sum, modulo $998244353$, of $f(P)$ over all permutations $P=(P_{1},P_{2},\\dots ,P_{N})$ of $(1,2,\\dots,N)$."},{"iden":"constraints","content":"*   $1\\leq K\\lt N\\leq 5000$\n*   $1\\leq A_{i}\\leq 10^{9}$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_{1}$ $A_{2}$ $\\cdots$ $A_{N}$"},{"iden":"sample input 1","content":"5 2\n3 4 5 2 1"},{"iden":"sample output 1","content":"1740\n\nFor $P=(1,2,3,4,5)$, the following edges form a spanning tree of $G$:\nthe edge between vertices $1$ and $2$ of weight $4$,\nthe edge between vertices $2$ and $3$ of weight $5$,\nthe edge between vertices $2$ and $4$ of weight $4$, and\nthe edge between vertices $4$ and $5$ of weight $2$,\nfor a total weight of $15$.\nIt is impossible to take a spanning tree with a smaller total edge weight, so $f(P)=15$.\nIn this way, it can be seen that the sum of $f(P)$ over all permutations $P$ of $(1,2,3,4,5)$ is $1740$, which should be printed."},{"iden":"sample input 2","content":"2 1\n167 924"},{"iden":"sample output 2","content":"1848"},{"iden":"sample input 3","content":"12 9\n22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740"},{"iden":"sample output 3","content":"660459584"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}