{"raw_statement":[{"iden":"problem statement","content":"A sequence of $n$ numbers, $S = (s_1, s_2, \\dots, s_n)$, is said to be _non-decreasing_ if and only if $s_i \\leq s_{i+1}$ holds for every $i$ $(1 \\leq i \\leq n - 1)$.\nGiven are non-decreasing sequences of $N$ integers each: $A = (a_1, a_2, \\dots, a_N)$ and $B = (b_1, b_2, \\dots, b_N)$.  \nConsider a non-decreasing sequence of $N$ integers, $C = (c_1, c_2, \\dots, c_N)$, that satisfies the following condition:\n\n*   $a_i \\leq c_i \\leq b_i$ for every $i$ $(1 \\leq i \\leq N)$.\n\nFind the number, modulo $998244353$, of sequences that can be $C$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 3000$\n*   $0 \\leq a_i \\leq b_i \\leq 3000$ $(1 \\leq i \\leq N)$\n*   The sequences $A$ and $B$ are non-decreasing.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $\\dots$ $a_N$\n$b_1$ $b_2$ $\\dots$ $b_N$"},{"iden":"sample input 1","content":"2\n1 1\n2 3"},{"iden":"sample output 1","content":"5\n\nThere are five sequences that can be $C$, as follows.\n\n*   $(1, 1)$\n*   $(1, 2)$\n*   $(1, 3)$\n*   $(2, 2)$\n*   $(2, 3)$\n\nNote that $(2, 1)$ does not satisfy the condition since it is not non-decreasing."},{"iden":"sample input 2","content":"3\n2 2 2\n2 2 2"},{"iden":"sample output 2","content":"1\n\nThere is one sequence that can be $C$, as follows.\n\n*   $(2, 2, 2)$"},{"iden":"sample input 3","content":"10\n1 2 3 4 5 6 7 8 9 10\n1 4 9 16 25 36 49 64 81 100"},{"iden":"sample output 3","content":"978222082\n\nBe sure to find the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}