Description

There is a polynomial function $f(x)$ whose highest power is $x^m$. Define a transformation $Q$:

Now given $f$ and $n, x$, compute $Q(f,n,x)\bmod998244353$.

For some reason, the function $f$ is given in point-value form. That is, $m+1$ numbers $a_0,a_1,⋯,a_m$ are given, and $f(x)=a_x$. It can be proven that this function is unique.

Input Format

The first line contains three integers $n, m, x$, with meanings as described above.

The second line contains $m+1$ integers, representing $a_0,a_1,⋯,a_m$.

Output Format

Output one number in one line as the answer, taken modulo $998,244,353$.

4 1 332748118
0 1

332748119

4 3 12
0 1 8 27

46704

Hint

Explanation for Sample $2$

After calculation, $f(x)=x^3$.

Constraints

For all testdata, it is guaranteed that $1≤n≤10^9$, $1≤m≤2×10^4$, and $0≤a_i,x<998,244,353$.

Translated by ChatGPT 5