103097: [Atcoder]ABC309 Ex - Simple Path Counting Problem

Problem Statement

We have a grid with $N$ rows and $M$ columns. We denote by $(i,j)$ the cell in the $i$-th row from the top and $j$-th column from the left.

You are given integer sequences $A=(A_1,A_2,\dots,A_K)$ and $B=(B_1,B_2,\dots,B_L)$ of lengths $K$ and $L$, respectively.

Find the sum, modulo $998244353$, of the answers to the following question over all integer pairs $(i,j)$ such that $1 \le i \le K$ and $1 \le j \le L$.

• A piece is initially placed at $(1,A_i)$. How many paths are there to take it to $(N,B_j)$ by repeating the following move $(N-1)$ times?
  • Let $(p,q)$ be the piece's current cell. Move it to $(p+1,q-1),(p+1,q)$, or $(p+1,q+1)$, without moving it outside the grid.

Constraints

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

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 4 1 2
1
1 2

Sample Output 1

4

For $(i,j)=(1,1)$, the following two paths are possible:

• $(1,1) \rightarrow (2,1) \rightarrow (3,1)$
• $(1,1) \rightarrow (2,2) \rightarrow (3,1)$

For $(i,j)=(1,2)$, the following two paths are possible:

• $(1,1) \rightarrow (2,1) \rightarrow (3,2)$
• $(1,1) \rightarrow (2,2) \rightarrow (3,2)$

Thus, the answer is $2 + 2 =4$.

Sample Input 2

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

Sample Output 2

137

Sample Input 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

Sample Output 3

941873621

问题描述

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

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

对于所有的整数对 $(i,j)$，使得 $1 \le i \le K$ 和 $1 \le j \le L$，找出以下问题答案的和（模 $998244353$）：

• 一块棋子最初放在 $(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