Polynomial Transformation

Given a polynomial function ( f(x) ) of degree ( m ) (its highest term is ( x^m )), we define a transformation ( Q ) as follows:

[ Q(f, n, x)=\sum_{k=0}^{n} f(k)\binom{n}{k} x^k (1-x)^{n-k} ]

The function ( f ) is provided in point-value form: you are given ( a_0, a_1, \dots, a_m ) such that ( f(i)=a_i ) for ( i=0,1,\dots,m ), which uniquely determines ( f(x) ).

Your task is to compute ( Q(f, n, x) \bmod 998244353 ).

inputFormat

The first line contains three integers ( m, n, x ) where ( m ) is the degree of the polynomial, and ( n ) and ( x ) are the parameters for transformation ( Q ). ( m+1 ) integers follow in the next line: ( a_0, a_1, \dots, a_m ), representing the values of ( f(0), f(1), \dots, f(m) ) respectively.

outputFormat

Output a single integer: the value of ( Q(f, n, x) \mod 998244353 ).

sample

2 3 1
1 2 3

4