AT_pakencamp_2022_day3_k Inner Product

長さ $ 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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_0 $ $ A_1 $ $ \ldots $ $ A_{N-1} $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $ $ C_0 $ $ C_1 $ $ \ldots $ $ C_{M-1} $ $ D_1 $ $ D_2 $ $ \ldots $ $ D_M $

答えを出力せよ。

### Sample Explanation 1 $ 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 $ が答えです。 ### Constraints - $ 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 $ - 入力は全て整数