题目背景

题目描述

小山即将参加 $n$ 场篮球比赛，他有一个多项式函数 $f(x)=a_0+a_1x^1+a_2x^2+\dots+a_kx^k$ 与 $m$ 个和为 $1$ 的数 $p_1,p_2,p_3,\dots,p_m$。

他所在的球队有 $\dfrac{f(i)}{\sum_{j=1}^n f(j)}$ 的概率在第 $i$ 场比赛中取得第一次胜利，这意味着前面的 $i-1$ 场都输了。

接下来，如果第 $i$ 场比赛中小山所在球队取得了胜利，则对于 $1\le j\le m$，他们有 $p_j$ 的概率在第 $i+j$ 场比赛取得下一次胜利，这意味着如果 $j\gt1$，第 $i+1$ 场到第 $i+j-1$ 场都输了（若 $i+j>n$，则之后的比赛都输，没有再胜利）。

小山想知道他所在球队的期望胜利场数，你能帮帮他吗？

注意：在计算时，如果遇到分数（比如 $\dfrac{f(i)}{\sum_{j=1}^n f(j)}$），应使用分数取模形式。如果不知道什么是分数取模形式，参见 P2613 【模板】有理数取余。

为了方便你的计算，输入数据将直接给出 $p_i,a_i$ 对 $998244353$ 取模的结果。

输入格式

第一行 $3$ 个整数 $n, m, k$，含义如上所述。

第二行 $m$ 个整数，第 $i$ 个整数表示 $p_i$ 模 $998244353$ 的值。

第三行 $k + 1$ 个整数，第 $i$ 个整数表示 $a_{i - 1}$ 模 $998244353$ 的值。

注意是先输入 $p$ 再输入 $a$。

输出格式

一行一个数，表示答案模 $998244353$ 的值。

4 3 3
598946612 898419918 499122177
998244308 79 998244317 5

319837492

提示

样例解释

在第一组样例中：$p_1=0.2,p_2=0.3,p_3=0.5$；$f(1)=3,f(2)=9,f(3)=3,f(4)=15$。胜利场数期望为 $1.2988$。

数据范围

对于 $100\%$ 的数据，$1\le n\le 10^{18}$，$1\le m,k \le 50$，保证 $\sum_{j=1}^n f(j)$ 不被 $998244353$ 整除。