P10586 "ALFR Round 2" B Basketball Match.


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](https://www.luogu.com.cn/problem/P2613). To make computation easier, the input will directly give $p_i,a_i$ after taking modulo $998244353$.

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 one number in one line, the answer modulo $998244353$.

### 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 | Subtask | Score | Limit | | :----------: | :----------: | :----------: | | $0$ | $10$ | $n=1$ | | $1$ | $30$ | $n\le10^6$ | | $2$ | $60$ | - | 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