{"problem":{"name":"Lottery","description":{"content":"Takahashi is participating in a lottery. Each time he takes a draw, he gets one of the $N$ prizes available. Prize $i$ is awarded with probability $\\frac{W_i}{\\sum_{j=1}^{N}W_j}$. The results of the d","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc243_f"},"statements":[{"statement_type":"Markdown","content":"Takahashi is participating in a lottery.\nEach time he takes a draw, he gets one of the $N$ prizes available. Prize $i$ is awarded with probability $\\frac{W_i}{\\sum_{j=1}^{N}W_j}$. The results of the draws are independent of each other.\nWhat is the probability that he gets exactly $M$ different prizes from $K$ draws? Find it modulo $998244353$.\n\n## Constraints\n\n*   $1 \\leq K \\leq 50$\n*   $1 \\leq M \\leq N \\leq 50$\n*   $0 < W_i$\n*   $0 < W_1 + \\ldots + W_N < 998244353$\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$\n$W_1$\n$\\vdots$\n$W_N$\n\n[samples]\n\n## Note\n\nTo print a rational number, start by representing it as a fraction $\\frac{y}{x}$. Here, $x$ and $y$ should be integers, and $x$ should not be divisible by $998244353$ (under the Constraints of this problem, such a representation is always possible). Then, print the only integer $z$ between $0$ and $998244352$ (inclusive) such that $xz\\equiv y \\pmod{998244353}$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc243_f","tags":[],"sample_group":[["2 1 2\n2\n1","221832079\n\nEach draw awards Prize $1$ with probability $\\frac{2}{3}$ and Prize $2$ with probability $\\frac{1}{3}$.\nHe gets Prize $1$ at both of the two draws with probability $\\frac{4}{9}$, and Prize $2$ at both draws with probability $\\frac{1}{9}$, so the sought probability is $\\frac{5}{9}$.\nThe modulo $998244353$ representation of this value, according to Note, is $221832079$."],["3 3 2\n1\n1\n1","0\n\nIt is impossible to get three different prizes from two draws, so the sought probability is $0$."],["3 3 10\n499122176\n499122175\n1","335346748"],["10 8 15\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1","755239064"]],"created_at":"2026-03-03 11:01:14"}}