Problem Background

Gambler $\mathcal{CYJian}$ is back!

Problem Description

$\mathcal{tomoo}$ has decided to duel with $\mathcal{CYJian}$!

Given that $\mathcal{tomoo}$ has $\mathcal{N}$ poker cards, each with an $\mathcal{RP}$ value $\mathcal{A_i}$, and $\mathcal{CYJian}$ has $\mathcal{M}$ poker cards, each with an $\mathcal{RP}$ value $\mathcal{B_i}$.

$\mathcal{CYJian}$ and $\mathcal{tomoo}$ will each randomly select a continuous interval of cards from their decks to duel. The one whose interval's $\mathcal{RP}$ values sum to a higher total wins. Please help determine the probability of $\mathcal{tomoo}$ winning.

Input Format

• The first line contains two positive integers $\mathcal{N,M}$.
• The second line contains $N$ positive integers $\mathcal{A_i}$.
• The third line contains $M$ positive integers $\mathcal{B_i}$.

Output Format

Output a number representing the probability of $\mathcal{tomoo}$ winning. If the answer can be expressed as $\frac{P}{Q}$, output $\frac{P}{Q}\%998244353$ (refer to P3811 if unsure).

Sample Input and Output

Sample Input #1

5 5
1 2 3 4 5
1 3 5 7 9

Sample Output #1

754229067

Sample Input #2

10 15
7 8 5 1 2 3 6 5 4 1 
52 10 5 6 3 2 1 4 5 8 7 4 5 6 3

Sample Output #2

181952721

Sample Input #3

1 1
5
5

Sample Output #3

0

Sample Input #4

5 5
1254125 36521421 25362142 12514221 25362142
857412252 36322411 2236232 1254112 36224125

Sample Output #4

261761853

Sample Input #5

2 2
2 4
2 5

Sample Output #5

332748118

Notes

Sample Explanation

• Sample $3$: No matter how cards are drawn, the result is even, so the win rate is $0$.
• Sample $5$: There are $9$ possible ways, and tomoo wins in $3$ of them, giving a win rate of $1/3$.

Data Range

• For $20\%$ of the data, $0<N,M\le50$.
• For another $20\%$ of the data, $\sum_{i=1}^NA_i\le10^6,\sum_{j=1}^MB_j\le10^6$.
• For $100\%$ of the data, $0<N,M\le2000,0<A_i,B_i\le10^9$.

见题面 Input 部分

见题面 Output 部分