{"problem":{"name":"Kth Number","description":{"content":"We have a sequence of length $N$ consisting of integers between $0$ and $M$, inclusive: $A=(A_1,A_2,\\dots,A_N)$. Snuke will perform the following operations 1 and 2 in order. 1.  For each $i$ such th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc295_e"},"statements":[{"statement_type":"Markdown","content":"We have a sequence of length $N$ consisting of integers between $0$ and $M$, inclusive: $A=(A_1,A_2,\\dots,A_N)$.\nSnuke will perform the following operations 1 and 2 in order.\n\n1.  For each $i$ such that $A_i=0$, independently choose a uniform random integer between $1$ and $M$, inclusive, and replace $A_i$ with that integer.\n2.  Sort $A$ in ascending order.\n\nPrint the expected value of $A_K$ after the two operations, modulo $998244353$.\nHow to print a number modulo $998244353$? It can be proved that the sought expected value is always rational. Additionally, under the Constraints of this problem, when that value is represented as $\\frac{P}{Q}$ using two coprime integers $P$ and $Q$, it can be proved that there is a unique integer $R$ such that $R \\times Q \\equiv P\\pmod{998244353}$ and $0 \\leq R \\lt 998244353$. Print this $R$.\n\n## Constraints\n\n*   $1\\leq K \\leq N \\leq 2000$\n*   $1\\leq M \\leq 2000$\n*   $0\\leq A_i \\leq M$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$A_1$ $A_2$ $\\dots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc295_e","tags":[],"sample_group":[["3 5 2\n2 0 4","3\n\nIn the operation 1, Snuke will replace $A_2$ with an integer between $1$ and $5$. Let $x$ be this integer.\n\n*   If $x=1$ or $2$, we will have $A_2=2$ after the two operations.\n*   If $x=3$, we will have $A_2=3$ after the two operations.\n*   If $x=4$ or $5$, we will have $A_2=4$ after the two operations.\n\nThus, the expected value of $A_2$ is $\\frac{2+2+3+4+4}{5}=3$."],["2 3 1\n0 0","221832080\n\nThe expected value is $\\frac{14}{9}$."],["10 20 7\n6 5 0 2 0 0 0 15 0 0","617586310"]],"created_at":"2026-03-03 11:01:14"}}