Expected Wins in a Basketball Tournament

Little Shan is about to participate in ( n ) basketball games. He has a polynomial function [ f(x)=a_0+a_1x+a_2x^2+\cdots+a_kx^k ] whose coefficients ( a_0, a_1, \dots, a_k ) are given modulo (998244353), and ( m ) numbers ( p_1,p_2,\dots,p_m ) (also given modulo (998244353)) satisfying ( \sum_{j=1}^{m}p_j=1 ) (the distribution is given in modulo form).\n\nThe tournament works as follows. The probability that the team obtains its first win in the ( i )th game is [ \frac{f(i)}{\sum_{j=1}^{n}f(j)}] which means the team loses all games before ( i ). In other words, the first win occurs exactly at game ( i ) with that probability.\n\nAfter winning game ( i ), for each ( 1\le j\le m ), the team has a probability ( p_j ) to win in game ( i+j ) (provided that ( i+j\le n )); this win is considered the next victory, and it requires that all games between ( i+1 ) and ( i+j-1 ) are losses. If ( i+j>n ) then no further wins occur.\n\nLittle Shan wants to know the expected number of wins his team will achieve in the tournament. When computing the result, note that any fraction (for example, ( \frac{f(i)}{\sum_{j=1}^{n}f(j)} )) should be computed in the modular arithmetic sense (i.e. using rational numbers modulo (998244353)); for details on how to handle divisions modulo a prime, see, for example, the problem P2613 Template: Rational Numbers under Modulo.\n\nInput numbers are given as residues modulo (998244353), so you do not need to worry about converting them into fractions. Your task is to compute the expected number of wins (also modulo (998244353)).

inputFormat

The input consists of three lines.\n\nThe first line contains three integers ( n,\ m,\ k ) ( (1\le n\le 10^5,\ 1\le m\le 10^5,\ 0\le k\le 10^5) ), representing the number of games, the length of the probability vector, and the degree of the polynomial respectively.\n\nThe second line contains ( k+1 ) integers: ( a_0, a_1, \dots, a_k ) (each between 0 and (998244352)) — the coefficients of the polynomial ( f(x) ) given modulo (998244353).\n\nThe third line contains ( m ) integers: ( p_1, p_2, \dots, p_m ) (each between 0 and (998244352)) — the probabilities for the subsequent wins, given modulo (998244353) and satisfying ( \sum_{j=1}^{m} p_j=1 ) modulo (998244353).

outputFormat

Output a single integer — the expected number of wins in the tournament, computed modulo (998244353).

sample

5 2 1
1 1
499122177 499122177

486491124