Background

Problem Description

Xiaoshan is going to play $n$ basketball matches. He has a polynomial function $f(x)=a_0+a_1x^1+a_2x^2+\dots+a_kx^k$ and $m$ numbers $p_1,p_2,p_3,\dots,p_m$ whose sum is $1$.

His team has a probability of $\dfrac{f(i)}{\sum_{j=1}^n f(j)}$ to get the first victory in the $i$-th match, which means they lost all of the first $i-1$ matches.

Next, if Xiaoshan’s team wins the $i$-th match, then for $1\le j\le m$, they have probability $p_j$ to get the next victory in the $(i+j)$-th match. This means that if $j\gt1$, they lose from match $(i+1)$ to match $(i+j-1)$ (if $i+j>n$, then all matches after that are losses and there will be no more victories).

Xiaoshan wants to know the expected number of wins of his team. Can you help him?

Note: During calculation, if you meet fractions (such as $\dfrac{f(i)}{\sum_{j=1}^n f(j)}$), you should use the “fraction modulo” form. If you do not know what “fraction modulo” means, see P2613 Template: Modulo of Rational Numbers.

To make computation easier, the input will directly give $p_i,a_i$ after taking modulo $998244353$.

Input Format

The first line contains three integers $n, m, k$, with meanings as described above.

The second line contains $m$ integers. The $i$-th integer is the value of $p_i$ modulo $998244353$.

The third line contains $k + 1$ integers. The $i$-th integer is the value of $a_{i - 1}$ modulo $998244353$.

Note that $p$ is given before $a$.

Output Format

Output one number in one line, the answer modulo $998244353$.

4 3 3
598946612 898419918 499122177
998244308 79 998244317 5

319837492

Hint

Sample Explanation

In the first sample: $p_1=0.2,p_2=0.3,p_3=0.5$; $f(1)=3,f(2)=9,f(3)=3,f(4)=15$. The expected number of wins is $1.2988$.

Constraints

For $100\%$ of the testdata, $1\le n\le 10^{18}$, $1\le m,k \le 50$, and it is guaranteed that $\sum_{j=1}^n f(j)$ is not divisible by $998244353$.

Translated by ChatGPT 5