Four years after retiring, Kanan wants to climb from scratch to LGM again. However, since Kanan does not have much competitive programming ability left, she wants to use some methods to ensure she can reach LGM.

Kanan creates two CF accounts, both with an initial rating of $0$. Whenever there is a CF contest, Kanan will participate using the account with the lower current rating. After the contest ends, the rating of this account changes as follows:

• For each $i \in [-m, m]$, the probability that Kanan gains $i$ rating points is $w_i$, where $m$ is a known constant.
• The rating of the account used for the contest increases by $i$. Specifically, if the result is less than $0$, the rating is set to $\max(0, \text{rating} + i)$.

Kanan's goal is to have the account with the higher rating reach at least $n$ points. Now, she wants to know the expected number of CF contests she needs to participate in to reach this goal.

Input

The first line contains two integers $n$ and $m$, representing the target rating and the maximum magnitude of the rating change per contest.

The second line contains $2m+1$ integers, representing $w_{-m}, w_{-m+1}, \dots, w_{m}$. Here, $w_i$ indicates that the probability of the rating changing by $i$ is $w_i / 10^8$.

It is guaranteed that $\sum_{i=-m}^{m} w_i = 10^8$ and $\max(w_1, \dots, w_m) > 0$.

Output

Output a single integer representing the expected number of contests Kanan needs to participate in, modulo $998244353$.

Examples

Input 1

3 1
0 0 100000000

Output 1

5

Input 2

3 1
50000000 0 50000000

Output 2

18

Input 3

3 1
87654321 12345678 1

Output 3

218770954

Input 4

995 5
7596668 8305741 17378882 1042723 15454211 8130546 13423369 13541276 10497878 4211898 416808

Output 4

447430831

Subtasks

Subtask 1 (11 points): $1 \leq n, m \leq 25$.

Subtask 2 (21 points): $1 \leq n \leq 10^3, m = 1$.

Subtask 3 (37 points): $1 \leq n \leq 10^3, 1 \leq m \leq 15$.

Subtask 4 (31 points): $1 \leq n \leq 10^3, 1 \leq m \leq 50$.