問題文

長さ N の整数列 A = (A_0, A_1, \ldots, A_{N-1}),B=(B_1,B_2,\ldots,B_N) 、長さ M の整数列 C=(C_0,C_1,\ldots,C_{M-1}),D=(D_1,D_2,\ldots,D_M) と非負整数 K が与えられます。

ここで、長さ K+1 の数列 F=(F_0,F_1,\ldots,F_K),G=(G_0,G_1,\ldots,G_K) を以下で定義します。

• F_i = A_i\ (0 \le i < N)
• \displaystyle F_i = \sum_{k=1}^N B_kF_{i-k}\ (N \le i \le K)
• G_j = C_j\ (0 \le j < M)
• \displaystyle G_j = \sum_{k=1}^M D_kG_{j-k}\ (M \le j \le K)

\displaystyle \sum_{i=0}^K F_iG_i を 998244353 で割った余りを求めてください。

制約

• 1 \le N,M \le 50000
• 0 \le K \le 10^9
• 0 \le A_i < 998244353(0 \le i < N)
• 0 \le B_i < 998244353(1 \le i \le N)
• 0 \le C_i < 998244353(0 \le i < M)
• 0 \le D_i < 998244353(1 \le i \le M)
• B_N,D_M \neq 0
• 入力は全て整数

入力例 1

2 2 5
0 1
1 1
0 1
1 1

出力例 1

40

F=(0,1,1,2,3,5),G=(0,1,1,2,3,5) なので、 0\times 0 + 1\times 1+1\times 1+2\times 2+3\times 3+5 \times 5=40 が答えです。

入力例 2

3 2 1
1 2 3
4 5 6
7 8
9 10

出力例 2

23

入力例 3

6 7 924844033
3 1 4 1 5 9
2 6 5 3 5 8
9 7 9 3 2 3 8
4 6 2 6 4 3 3

出力例 3

142556085