問題文
長さ n の数列 S=(s1,s2,dots,sn) がすべての i (1leqileqn−1) に対して sileqsi+1 を満たすとき、かつそのときに限り「数列 S は広義単調増加である」と呼びます。
広義単調増加な長さ N の整数列 A=(a1,a2,dots,aN),B=(b1,b2,dots,bN) が与えられます。
このとき、次の条件を満たす広義単調増加な長さ N の整数列 C=(c1,c2,dots,cN) を考えます。
- すべての i (1leqileqN) に対して aileqcileqbi が成り立つ。
整数列 C としてあり得る数列の個数を 998244353 で割ったあまりを求めてください。
制約
- 1leqNleq3000
- 0leqaileqbileq3000 (1leqileqN)
- 整数列 A,B は広義単調増加である。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
a1 a2 dots aN
b1 b2 dots bN
出力
C としてあり得る数列の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
出力例 1
C としてあり得る数列は次の 5 個です。
- (1,1)
- (1,2)
- (1,3)
- (2,2)
- (2,3)
数列 (2,1) は広義単調増加でないため条件を満たさないことに注意してください。
入力例 2
出力例 2
C としてあり得る数列は次の 1 個です。
入力例 3
出力例 3
個数を 998244353 で割ったあまりを求めることに注意してください。