Time limit 2 seconds
Memory limit 64Mb
Input standard input or border.in
Output standard output or border.out

Let w and S – two integer sequences and we define a function enter image description here.

If the Border(S) is an empty set then f(S)=1 by definition.

Integer enter image description here, when and only when 1 ≤ k < |S| and enter image description here.

Now you are given two integers n, m, and partially a sequence w (size of w is n). You need to calculate the sum of f(S) among all the integer sequences S, that should satisfy:

The length of S is n.
, enter image description here1 ≤ Si ≤ m
.
Print the answer module 998244353.

Input format
The first line of the input contains two integers n (1 ≤ n ≤ 500), and m (2 ≤ m ≤ 998244352).

The second line contains n – 1 integers, w1,w2,…,wn – 1 (0 ≤ wi ≤ 998244352). Note that wn is left unknown.

Output format
Print one integer representing the answer.

Sample
Input
3 2
2 2
Output
16
Notes
“111“, “222“ : f(S) = 4.

“121“, “212“ : f(S) = 2.

“122“, “112“, “211“, “221“ : f(S) = 1.

So the answer is 4 × 2 + 2 × 2 + 1 × 4 = 16.

i just need the code man. i think its a good challenge for ppl