{"problem":{"name":"Balls in Boxes","description":{"content":"We have $N$ boxes numbered $1$ to $N$. Initially, Box $i$ contains $A_i$ balls. You will repeat the following operation $K$ times. *   Choose one box out of the $N$ uniformly at random (each time ind","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc231_g"},"statements":[{"statement_type":"Markdown","content":"We have $N$ boxes numbered $1$ to $N$. Initially, Box $i$ contains $A_i$ balls.\nYou will repeat the following operation $K$ times.\n\n*   Choose one box out of the $N$ uniformly at random (each time independently). Add one ball to the chosen box.\n\nLet $B_i$ be the number of balls in Box $i$ after the $K$ operations, and the **score** be the product of the numbers of balls, $\\prod_{i=1}^{N}B_i$.\nFind the expected value of the score modulo $998244353$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 1000$\n*   $1 \\leq K \\leq 10^9$\n*   $0 \\leq A_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $\\ldots$ $A_N$\n\n[samples]\n\n## Notes\n\nWhen the expected value in question is represented as an irreducible fraction $p/q$, there uniquely exists an integer $r$ such that $rq\\equiv p \\pmod{998244353}$ and $0\\leq r < 998244353$ under the Constraints of this problem. This $r$ is the value we seek.","is_translate":false,"language":"English"}],"meta":{"iden":"abc231_g","tags":[],"sample_group":[["3 1\n1 2 3","665496245\n\nAfter the operation, the score will be as follows.\n\n*   When choosing Box $1$ in the operation, $2\\times 2\\times 3=12$.\n*   When choosing Box $2$ in the operation, $1\\times 3\\times 3=9$.\n*   When choosing Box $3$ in the operation, $1\\times 2\\times 4=8$.\n\nTherefore, the expected value in question is $\\frac{1}{3}(12+9+8)=\\frac{29}{3}$. This value modulo $998244353$ is $665496245$."],["2 2\n1 2","499122182\n\nAfter the operations, the score will be as follows.\n\n*   When choosing Box $1$ in the first operation and Box $1$ in the second, $3\\times 2=6$.\n*   When choosing Box $1$ in the first operation and Box $2$ in the second, $2\\times 3=6$.\n*   When choosing Box $2$ in the first operation and Box $1$ in the second, $2\\times 3=6$.\n*   When choosing Box $2$ in the first operation and Box $2$ in the second, $1\\times 4=4$.\n\nTherefore, the expected value in question is $\\frac{1}{4}(6+6+6+4)=\\frac{11}{2}$."],["10 1000000000\n998244350 998244351 998244352 998244353 998244354 998244355 998244356 998244357 998244358 998244359","138512322"]],"created_at":"2026-03-03 11:01:14"}}