{"raw_statement":[{"iden":"problem statement","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)."},{"iden":"notes","content":"It 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$."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"3 3\n1 1\n1 2\n2 3"},{"iden":"sample output 1","content":"499122180\n\nThe sought expected value is $\\frac{7}{2}$.\nWe have $499122180 \\times 2 \\equiv 7\\pmod{998244353}$, so $499122180$ should be printed."},{"iden":"sample input 2","content":"13 10\n3 5\n5 9\n3 12\n1 13\n9 11\n12 13\n2 4\n9 12\n9 11\n7 11"},{"iden":"sample output 2","content":"10"},{"iden":"sample input 3","content":"100 11\n22 43\n84 93\n12 71\n49 56\n8 11\n1 61\n13 80\n26 83\n23 100\n80 85\n9 89"},{"iden":"sample output 3","content":"499122193"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}