Solving a Polynomial Recurrence

Consider an infinite sequence \(\{a_i\}_{i\ge 0}\) satisfying for all \(n\ge m\) the recurrence

\(\displaystyle \sum_{k=0}^{m} a_{n-k} \; P_k(n) = 0\),

where each \(P_k(x)\) is a polynomial in \(x\) of degree at most \(d\). You are given the coefficients of all the \(m+1\) polynomials \(P_0,P_1,\dots,P_m\) and the first \(m\) terms \(a_0,a_1,\dots,a_{m-1}\) of the sequence. Your task is to compute \(a_n\) modulo \(998244353\). It is guaranteed that for every integer \(n\ge m\), \(P_0(n) \not\equiv 0 \pmod{998244353}\), so that the recurrence uniquely defines \(a_n\).

The recurrence can be rearranged (for \(n\ge m\)) as:

[ a_n = -\frac{a_{n-1}P_1(n)+a_{n-2}P_2(n)+\cdots+a_{n-m}P_m(n)}{P_0(n)} \pmod{998244353}. ]

Please note that all arithmetic is to be performed modulo \(998244353\).

inputFormat

The input consists of the following:

• The first line contains three integers \(m\), \(d\) and \(n\) (with \(n \ge 0\)), where \(m\) is the number of initial terms given, \(d\) is the maximum degree of the polynomials, and \(n\) is the index of the term to compute.
• Then follow \(m+1\) lines. The \(k\)-th of these lines (for \(0 \le k \le m\)) contains \(d+1\) integers: the coefficients of the polynomial \(P_k(x)=c_{k,0}+c_{k,1}x+\cdots+c_{k,d}x^{d}\). (It is allowed that several leading coefficients are zero.)
• The last line contains \(m\) integers: \(a_0,a_1,\dots,a_{m-1}\), the initial values of the sequence.

outputFormat

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

sample

2 1 5
1 0
0 1
1 1
1 2

7