Description

已知递推式：

$$a_n = P(n) + \sum\limits_{i=1}^k f_i \times a_{n-i}$$

其中 $P(x)$ 是一个 $m$ 次多项式。

给定 $f_1,f_2,\dots,f_k$，$a_0,a_1,\dots,a_{k-1}$，和 $P(x)$ 的各项系数，求 $a_n$。
答案对 $998244353$ 取模。

Input Format

第一行三个正整数 $n,m,k$。
第二行 $k$ 个整数，表示 $a_0,a_1,\dots,a_{k-1}$。
第三行 $k$ 个整数，表示 $f_1,f_2,\dots,f_k$。
第四行 $m+1$ 个整数，由低到高的表示 $P(x)$ 的系数。

Output Format

输出一行一个整数表示答案。

40 5 6
1 2 3 5 8 13
1 3 4 9 6 7
1 1 4 5 1 4

349344375

Hint

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^9$，$1\le m,k \le 30000$。
除第一行外，输入的所有数在 $[0,998244353)$ 范围内。

数据有一定梯度。