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)$，具体定义如下： - 对于 $0 \le i < N$，有 $F_i = A_i$； - 对于 $N \le i \le K$，有 $F_i = \sum_{k=1}^N B_k F_{i-k}$； - 对于 $0 \le j < M$，有 $G_j = C_j$； - 对于 $M \le j \le K$，有 $G_j = \sum_{k=1}^M D_k G_{j-k}$。 请你求出 $\displaystyle \sum_{i=0}^K F_i G_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$

请输出答案。

## 样例解释 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$，因此答案为 $40$。 ## 约束条件 - $1 \le N, M \le 50000$ - $0 \le K \le 10^9$ - $0 \le A_i < 998244353 \quad (0 \le i < N)$ - $0 \le B_i < 998244353 \quad (1 \le i \le N)$ - $0 \le C_i < 998244353 \quad (0 \le i < M)$ - $0 \le D_i < 998244353 \quad (1 \le i \le M)$ - $B_N, D_M \neq 0$ - 输入均为整数。 由 ChatGPT 5 翻译