{"problem":{"name":"The Majority","description":{"content":"There are $K$ boxes numbered $1$ to $K$. Initially, all boxes are empty. Snuke has some balls with integers from $1$ to $N$ written on them. Among them, $a_i$ balls have the number $i$. Balls with the","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc134_c"},"statements":[{"statement_type":"Markdown","content":"There are $K$ boxes numbered $1$ to $K$. Initially, all boxes are empty.\nSnuke has some balls with integers from $1$ to $N$ written on them. Among them, $a_i$ balls have the number $i$. Balls with the same integer written on them cannot be distinguished.\nSnuke has decided to put all of his balls in the boxes. He wants the balls with the number $1$ to have a majority in every box. In other words, in every box, the number of balls with $1$ should be greater than that of the other balls.\nFind the number of such ways to put the balls in the boxes, modulo $998244353$.\nTwo ways are distinguished when there is a pair of integers $(i,j)$ satisfying $1 \\leq i \\leq K, 1 \\leq j \\leq N$ such that the numbers of balls with $j$ in Box $i$ are different.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq K \\leq 200$\n*   $1 \\leq a_i < 998244353$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$ \n$a_1$ $\\cdots$ $a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc134_c","tags":[],"sample_group":[["2 2\n3 1","2\n\n*   There are two ways to put the balls so that the balls with the number $1$ will be in the majority.\n*   One way to do so is to put two of the balls with $1$ in Box $1$ and the other one in Box $2$, and put the one ball with $2$ in Box $1$."],["2 1\n1 100","0\n\n*   There may be no way to put the balls in the boxes to meet the requirement."],["20 100\n1073813 90585 41323 52293 62633 28788 1925 56222 54989 2772 36456 64841 26551 92115 63191 3603 82120 94450 71667 9325","313918676\n\n*   Be sure to find the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}