#abc222d. [abc222_d]Between Two Arrays

[abc222_d]Between Two Arrays

問題文

長さ nn の数列 S=(s1,s2,dots,sn)S = (s_1, s_2, \\dots, s_n) がすべての ii (1leqileqn1)(1 \\leq i \\leq n - 1) に対して sileqsi+1s_i \\leq s_{i+1} を満たすとき、かつそのときに限り「数列 SS は広義単調増加である」と呼びます。

広義単調増加な長さ NN の整数列 A=(a1,a2,dots,aN),B=(b1,b2,dots,bN)A = (a_1, a_2, \\dots, a_N), B = (b_1, b_2, \\dots, b_N) が与えられます。
このとき、次の条件を満たす広義単調増加な長さ NN の整数列 C=(c1,c2,dots,cN)C = (c_1, c_2, \\dots, c_N) を考えます。

  • すべての ii (1leqileqN)(1 \\leq i \\leq N) に対して aileqcileqbia_i \\leq c_i \\leq b_i が成り立つ。

整数列 CC としてあり得る数列の個数を 998244353998244353 で割ったあまりを求めてください。

制約

  • 1leqNleq30001 \\leq N \\leq 3000
  • 0leqaileqbileq30000 \\leq a_i \\leq b_i \\leq 3000 (1leqileqN)(1 \\leq i \\leq N)
  • 整数列 A,BA,B は広義単調増加である。
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN a1a_1 a2a_2 dots\\dots aNa_N b1b_1 b2b_2 dots\\dots bNb_N

出力

CC としてあり得る数列の個数を 998244353998244353 で割ったあまりを出力せよ。


入力例 1

2
1 1
2 3

出力例 1

CC としてあり得る数列は次の 55 個です。

  • (1,1)(1, 1)
  • (1,2)(1, 2)
  • (1,3)(1, 3)
  • (2,2)(2, 2)
  • (2,3)(2, 3)

数列 (2,1)(2, 1) は広義単調増加でないため条件を満たさないことに注意してください。


入力例 2

3
2 2 2
2 2 2

出力例 2

CC としてあり得る数列は次の 11 個です。

  • (2,2,2)(2, 2, 2)

入力例 3

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

出力例 3

978222082

個数を 998244353998244353 で割ったあまりを求めることに注意してください。