$\pi+e$ often sleeps during high school math classes, yet he manages to $AK$ every exam, which makes his deskmate Yezi admire him greatly.

One day, the teacher was lecturing on binomial distribution problems:

(2010 Tianjin, 18 modified)
A shooter has a probability p=1/3 of hitting the target in each shot, and the results of each shot are independent and do not affect each other.
Let X be the number of hits in 4 shots. Find the mathematical expectation and the variance of the expectation of X.
(Answer: 4/3, 8/9)

The teacher said: "For this, the expectation of a binomial distribution is $np$, and the variance is $np(1-p)$. If you don't believe it, calculate it yourselves after class."

Upon hearing that there was an extra credit problem, $\pi+e$ immediately perked up and solved the problem easily using his "black technology" of "generating function differentiation." He also took the opportunity to explain it to Yezi.

One day during the 2016 summer vacation, $\pi+e$ suddenly remembered this incident. He thought about it and strengthened the original problem into the following form:

There is a polynomial function $f(x)$ with a maximum degree of $x^m$. Define the transformation $Q$:

$$Q(f,n,x) = \sum_{k = 0}^{n}f(k){n\choose k}x^k(1 - x) ^{n - k}$$

Now, given the function $f$ and $n, x$, calculate $Q(f,n,x)\bmod 998244353$.

However, as everyone knows, one loses a lot of intelligence after taking the college entrance exam. $\pi+e$ found that he had forgotten how to use his black technology; he called Yezi, but Yezi said he didn't remember either.

Can you help him?

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

Input

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, \dots, a_m$.

Output

Output a single integer representing the answer, modulo $998,244,353$.

Examples

Input 1

4 1 332748118
0 1

Output 1

332748119

Note 1

Note that $332748118 \equiv \frac{1}{3} \pmod{ 998244353 }$, $332748119 \equiv \frac{4}{3} \pmod{ 998244353 }$, and $f(x)=x$. The expression requested in the problem is:

$$\sum_{k=0}^4 k{4\choose k}\left(\frac{1}{3}\right)^k\left(\frac{2}{3}\right)^{4-k}=\frac{4}{3}$$

This is the expression for calculating the expectation in the binomial distribution example at the beginning of the problem.

Input 2

4 3 12
0 1 8 27

Output 2

46704

Note 2

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

Input 3

See the provided files.

Constraints

For all test cases, it is guaranteed that $1 \le n \le 10^{9},\ 1 \le m \le 2 \times 10^{4},\ 0\le a_i,x< 998,244,353$.