简单路径计数

题目描述

我们有一个 $N$ 行 $M$ 列的网格。用 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

给定长度为 $K$ 和 $L$ 的整数序列 $A=(A_1,A_2,\dots,A_K)$ 和 $B=(B_1,B_2,\dots,B_L)$。

对于所有满足 $1 \le i \le K$ 且 $1 \le j \le L$ 的整数对 $(i,j)$,考虑以下问题,求所有答案之和,对 $998244353$ 取模。

一个棋子最初位于 $(1,A_i)$。通过重复执行以下移动 $(N-1)$ 次,有多少种路径可以将其移动到 $(N,B_j)$?

设 $(p,q)$ 为棋子的当前位置。将棋子移动到 $(p+1,q-1)$、$(p+1,q)$ 或 $(p+1,q+1)$,但不能移出网格。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $K$ $L$
$A_1$ $A_2$ $\dots$ $A_K$
$B_1$ $B_2$ $\dots$ $B_L$

输出格式

输出答案。

样例

3 4 1 2
1
1 2

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$。

5 8 4 5
3 1 4 1
2 7 1 8 2

137

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

941873621

数据范围

• $1 \le N \le 10^9$
• $1 \le M,K,L \le 10^5$
• $1 \le A_i,B_j \le M$