AT_abc309_h [ABC309Ex] Simple Path Counting Problem

[problemUrl]: https://atcoder.jp/contests/abc309/tasks/abc309_h $ N $ 行 $ M $ 列のマス目があります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と呼ぶこととします。 長さ $ K $ の整数列 $ A=(A_1,A_2,\dots,A_K) $ と長さ $ L $ の整数列 $ 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 $

答えを出力せよ。

### 制約 - $ 1\ \le\ N\ \le\ 10^9 $ - $ 1\ \le\ M,K,L\ \le\ 10^5 $ - $ 1\ \le\ A_i,B_j\ \le\ M $ ### Sample Explanation 1 $ (i,j)=(1,1) $ のとき、駒の移動方法は以下の $ 2 $ 通りです。 - $ (1,1)\ \rightarrow\ (2,1)\ \rightarrow\ (3,1) $ - $ (1,1)\ \rightarrow\ (2,2)\ \rightarrow\ (3,1) $ $ (i,j)=(1,2) $ のとき、駒の移動方法は以下の $ 2 $ 通りです。 - $ (1,1)\ \rightarrow\ (2,1)\ \rightarrow\ (3,2) $ - $ (1,1)\ \rightarrow\ (2,2)\ \rightarrow\ (3,2) $ よって、答えは $ 2\ +\ 2\ =4 $ です。