赌神:决斗
题目背景
**赌神 $\mathcal{CYJian}$,他回来了!**
题目描述
**$\mathcal{tomoo}$** 决定与 **$\mathcal{CYJian}$** 进行决斗!
已知 **$\mathcal{tomoo}$** 有 $\mathcal{N}$ 张扑克牌,每张扑克牌有一个$\mathcal{RP}$值$\mathcal{A_i}$, **$\mathcal{CYJian}$** 有$\mathcal{M}$张扑克牌,每张扑克牌有一个$\mathcal{RP}$值$\mathcal{B_i}$。
**$\mathcal{CYJian}$** 与 **$\mathcal{tomoo}$** 将会各自从他们的牌里任意取一段**连续区间**的牌决斗,谁的区间内的牌的$\mathcal{RP}$值的和更大,谁就赢了,请你帮忙求出 **$\mathcal{tomoo}$** 赢的概率。
输入输出格式
输入格式
- 第一行 $2$ 个正整数 $\mathcal{N,M}$
- 第二行 $N$ 个正整数 $\mathcal{A_i}$
- 第三行 $M$ 个正整数 $\mathcal{B_i}$
输出格式
一个数表示 **$\mathcal{tomoo}$** 获胜的概率,如果答案可以表示成 $\frac{P}{Q}$ 的形式,则输出 $\frac{P}{Q}\%998244353$(不懂的左转[P3811](https://www.luogu.org/problemnew/show/P3811))
输入输出样例
输入样例 #1
5 5
1 2 3 4 5
1 3 5 7 9
输出样例 #1
754229067
输入样例 #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
输出样例 #2
181952721
输入样例 #3
1 1
5
5
输出样例 #3
0
输入样例 #4
5 5
1254125 36521421 25362142 12514221 25362142
857412252 36322411 2236232 1254112 36224125
输出样例 #4
261761853
输入样例 #5
2 2
2 4
2 5
输出样例 #5
332748118
说明
### 样例解释
- 样例 $3$:不管怎么抽都是平均,胜率为 $0$
- 样例 $5$:共有 $9$ 种方案,其中 $3$ 次 **tomoo** 会赢,胜率为 $1/3$
### 数据范围
- 对于 $20\%$ 的数据,$0<N,M\le50$
- 对于另外 $20\%$ 的数据,$\sum_{i=1}^NA_i\le10^6,\sum_{j=1}^MB_j\le10^6$
- 对于$100\%$的数据,$0<N,M\le2000,0<A_i,B_i\le10^9$