{"problem":{"name":"Gachapon","description":{"content":"Snuke found a random number generator. It generates an integer between $0$ and $N-1$ (inclusive). An integer sequence $A_0, A_1, \\cdots, A_{N-1}$ represents the probability that each of these integers","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc038_e"},"statements":[{"statement_type":"Markdown","content":"Snuke found a random number generator. It generates an integer between $0$ and $N-1$ (inclusive). An integer sequence $A_0, A_1, \\cdots, A_{N-1}$ represents the probability that each of these integers is generated. The integer $i$ ($0 \\leq i \\leq N-1$) is generated with probability $A_i / S$, where $S = \\sum_{i=0}^{N-1} A_i$. The process of generating an integer is done independently each time the generator is executed.\nNow, Snuke will repeatedly generate an integer with this generator until the following condition is satisfied:\n\n*   For every $i$ ($0 \\leq i \\leq N-1$), the integer $i$ has been generated at least $B_i$ times so far.\n\nFind the expected number of times Snuke will generate an integer, and print it modulo $998244353$. More formally, represent the expected number of generations as an irreducible fraction $P/Q$. Then, there exists a unique integer $R$ such that $R \\times Q \\equiv P \\pmod{998244353},\\ 0 \\leq R < 998244353$, so print this $R$.\nFrom the constraints of this problem, we can prove that the expected number of generations is a finite rational number, and its integer representation modulo $998244353$ can be defined.\n\n## Constraints\n\n*   $1 \\leq N \\leq 400$\n*   $1 \\leq A_i$\n*   $\\sum_{i=0}^{N-1} A_i \\leq 400$\n*   $1 \\leq B_i$\n*   $\\sum_{i=0}^{N-1} B_i \\leq 400$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_0$ $B_0$\n$A_1$ $B_1$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc038_e","tags":[],"sample_group":[["2\n1 1\n1 1","3\n\nThe expected number of times Snuke will generate an integer is $3$."],["3\n1 3\n2 2\n3 1","971485877\n\nThe expected number of times Snuke will generate an integer is $132929/7200$."],["15\n29 3\n78 69\n19 15\n82 14\n9 120\n14 51\n3 7\n6 14\n28 4\n13 12\n1 5\n32 30\n49 24\n35 23\n2 9","371626143"]],"created_at":"2026-03-03 11:01:14"}}