{"problem":{"name":"Ex - Random Painting","description":{"content":"There are $N$ squares numbered $1$ to $N$. Initially, all squares are painted white. Additionally, there are $M$ balls numbered $1$ to $M$ in a box. We repeat the procedure below until all squares are","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc242_h"},"statements":[{"statement_type":"Markdown","content":"There are $N$ squares numbered $1$ to $N$. Initially, all squares are painted white.\nAdditionally, there are $M$ balls numbered $1$ to $M$ in a box.\nWe repeat the procedure below until all squares are painted black.\n\n1.  Pick up a ball from a box uniformly at random.\n2.  Let $x$ be the index of the ball. Paint Squares $L_x, L_x+1, \\ldots, R_x$ black.\n3.  Return the ball to the box.\n\nFind the expected value of the number of times the procedure is done, modulo $998244353$ (see Notes).\n\n## Constraints\n\n*   $1 \\leq N,M \\leq 400$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   For every square $i$, there is an integer $j$ such that $L_j \\leq i \\leq R_j$.\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$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\hspace{0.5cm}\\vdots$\n$L_M$ $R_M$\n\n[samples]\n\n## Notes\n\nIt can be proved that the sought expected value is always a rational number. 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 uniquely exists an integer $R$ such that $R \\times Q \\equiv P\\pmod{998244353}$ and $0 \\leq R \\lt 998244353$. You should find this $R$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc242_h","tags":[],"sample_group":[["3 3\n1 1\n1 2\n2 3","499122180\n\nThe sought expected value is $\\frac{7}{2}$.\nWe have $499122180 \\times 2 \\equiv 7\\pmod{998244353}$, so $499122180$ should be printed."],["13 10\n3 5\n5 9\n3 12\n1 13\n9 11\n12 13\n2 4\n9 12\n9 11\n7 11","10"],["100 11\n22 43\n84 93\n12 71\n49 56\n8 11\n1 61\n13 80\n26 83\n23 100\n80 85\n9 89","499122193"]],"created_at":"2026-03-03 11:01:14"}}