{"problem":{"name":"Priority Queue 2","description":{"content":"You are given a multiset of integers with $N$ elements: $A=\\lbrace A_1,A_2,...,A_N \\rbrace$. It is guaranteed that every element of $A$ is between $1$ and $M$ (inclusive). Let us repeat the following ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc139_d"},"statements":[{"statement_type":"Markdown","content":"You are given a multiset of integers with $N$ elements: $A=\\lbrace A_1,A_2,...,A_N \\rbrace$. It is guaranteed that every element of $A$ is between $1$ and $M$ (inclusive).\nLet us repeat the following operation $K$ times.\n\n*   Choose an integer between $1$ and $M$ (inclusive) and add it to $A$. Then, delete the $X$\\-th smallest value in $A$.\n\nHere, the $X$\\-th smallest value in $A$ is the $X$\\-th value from the front in the sequence of the elements of $A$ sorted in non-decreasing order.\nThere are $M^K$ ways to choose an integer $K$ times between $1$ and $M$. Assume that, for each of these ways, we have found the sum of the elements of $A$ after the operations with the corresponding choices. Find the sum, modulo $998244353$, of the $M^K$ values computed.\n\n## Constraints\n\n*   $1 \\le N,M,K \\le 2000$\n*   $1 \\le X \\le N+1$\n*   $1 \\le A_i \\le M$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $K$ $X$\n$A_1$ $A_2$ $\\dots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc139_d","tags":[],"sample_group":[["2 4 2 1\n1 3","99\n\nWe start with $A={1,3}$. Here is an example of how we do the operations.\n\n*   Add $4$ to $A$, making $A={1,3,4}$. Then, delete the $1$\\-st smallest value, making $A={3,4}$.\n    \n*   Add $3$ to $A$, making $A={3,3,4}$. Then, delete the $1$\\-st smallest value, making $A={3,4}$.\n    \n\nIn this case, the sum of the elements of $A$ after the operations is $3+4=7$."],["5 9 6 3\n3 7 1 9 9","15411789"]],"created_at":"2026-03-03 11:01:13"}}