Ta định nghĩa dãy số nguyên \(\left[s_1,s_2,...,s_m\right]\) là một dãy không giảm khi và chỉ khi \(s_i\le s_{i+1}\) với mọi \(1\le i < m\).

Cho trước hai dãy không giảm \([l_1, l_2,...,l_n]\) và \([r_1, r_2,...,r_n]\), bạn hãy đếm số lượng dãy không giảm \([a_1,a_2,...,a_n]\) sao cho \(l_i\le a_i\le r_i\) với mọi \(1\le i\le n\) nhé! Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(998244353\).

Input

• Dòng đầu chứa số nguyên \(n\) \(\left(1\leq n\leq 3000\right)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(l_1\), \(l_2\),..., \(l_n\). Dữ liệu đảm bảo dãy \(l\) là một dãy không giảm và các phần tử đều có giá trị không vượt quá \(3000\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(r_1\), \(r_2\),..., \(r_n\). Dữ liệu đảm bảo dãy \(r\) là một dãy không giảm và các phần tử đều có giá trị không vượt quá \(3000\).
• Dữ liệu đảm bảo \(l_i\le r_i\) với mọi \(1\le i\le n\).

Output

• In ra một số nguyên thể hiện số lượng dãy không giảm thỏa mãn sau khi \(\text{mod}\) \(998244353\).

Ví dụ

Sample input 01

2
1 1
2 3

Sample output 01

5

Giải thích

Có \(5\) dãy không giảm thỏa mãn: \([1,1]\), \([1,2]\), \([1,3]\), \([2,2]\), và \([2,3]\).

Sample input 02

3
100 100 100
100 100 100

Sample output 02

1

Sample input 03

4
1 2 3 4 5
5 6 7 8 9

Sample output 03

126