分数: 650 点
问题陈述
我们有一个网格 N 行和 M 列。 我们表示为 (i,j) 中的单元格 i从顶部开始的第行和 j左起第 列。
给定整数序列 A=(A_1,A_2,\dots,A_K) 和 B=(B_1,B_2,\dots,B_L) 长度 K 和 L。
求总和,取模 998244353,关于所有整数对的以下问题的答案 (i,j) 这样 1 \le i \le K 和 1 \le j \le L.
- 一块最初放置在 (1,A_i)。 有多少条路可以到达 (N,B_j) 重复以下动作 (N-1) 次?
- 让 (p,q) 是该作品的当前单元格。 将其移至 (p+1,q-1),(p+1,q),或 (p+1,q+1),而不将其移出网格。
约束
- 1 \le N \le 10^9
- 1 \le M,K,L \le 10^5
- 1 \le A_i,B_j \le M
输入
输入由标准输入按以下格式给出:
N M K L A_1 A_2 \dots A_K B_1 B_2 \dots B_L
输出
打印答案。
示例输入 1
3 4 1 2 1 1 2
示例输出 1
4
对于 (i,j)=(1,1),以下两条路径是可能的:
- (1,1) \rightarrow (2,1) \rightarrow (3,1)
- (1,1) \rightarrow (2,2) \rightarrow (3,1)
对于 (i,j)=(1,2),以下两条路径是可能的:
- (1,1) \rightarrow (2,1) \rightarrow (3,2)
- (1,1) \rightarrow (2,2) \rightarrow (3,2)
因此,答案是 2 + 2 =4.
示例输入 2
5 8 4 5 3 1 4 1 2 7 1 8 2
示例输出 2
137
示例输入 3
883671387 87719 10 12 86879 64174 47274 41688 17713 50897 53989 7210 30894 5714 60358 28835 48036 48450 67149 36558 35929 69025 77539 19195 60762 60721
示例输出 3
941873621