题目背景

NaCly_Fish 一到机房，所有做题的人便都看着她笑。有的叫道，“鱼鱼，你怎么又爆零了！”她不回答，对教练说：“要两道数学题，一道数据结构。”便打开电脑。他们又故意的高声嚷道，“你怎么连 exgcd 都写不对了！”......

NaCly_Fish 自己知道不能和同机房的神仙们谈天，便只好向隔壁初一的说话。有一回对我说道，“你学过 OI 么？”我略略点一点头。他说，“学过 OI，...... 我便考你一考。常系数线性齐次递推，怎样算的？”我想，机房垫底 AFO 的人，也配考我么？便回过脸去，不再理会。NaCly_Fish 等了许久，很恳切的说道，“不会算罢？…… 我教给你，记着！这算法应该好好记着，将来比赛的时候，做题要用。”我懒懒的答她道，“谁要你教，不是把递推系数写在矩阵第一列，剩下斜着放 $1$，再快速幂么？”NaCly_Fish 显出极高兴的样子，将两个指头的长指甲敲着课桌，点头说，“对呀对呀！...... 这还有四样求法，你知道么？”......

---

NaCly_Fish 看见了这题，她根本不会做。
看在她那么菜的份上，请您做了这题，帮帮她吧。

题目描述

已知递推式：

$$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$ 取模。

输入格式

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

输出格式

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

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

349344375

提示

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

数据有一定梯度。