Recurrence with Polynomial Inhomogeneity

Given the recurrence relation [ a_n = P(n) + \sum_{i=1}^{k} f_i \times a_{n-i}, ] where (P(x)) is a polynomial of degree (m) with coefficients provided (in increasing order, i.e., constant term first), you are given the coefficients (f_1, f_2, \dots, f_k), the initial values (a_0, a_1, \dots, a_{k-1}) and the (m+1) coefficients of (P(x)). Your task is to compute (a_n \bmod 998244353).

inputFormat

The input consists of four lines:

1. Three integers k m n where k is the number of recurrence coefficients, m is the degree of the polynomial \(P(x)\), and n is the index of the term to compute.
2. k integers: f1, f2, ..., fk.
3. k integers: a0, a1, ..., ak-1 (initial values).
4. m+1 integers: the coefficients of \(P(x)\) in increasing order (i.e. constant term, coefficient of \(x\), ..., coefficient of \(x^m\)).

It is guaranteed that all the values needed are provided in the given order.

outputFormat

Output a single integer: \(a_n \bmod 998244353\).

sample

2 1 4
1 1
1 1
1 0

9