Master pb likes to play 2048.

Master pb plays 2048 on a $1\times n$ grid, where initially all $n$ cells are empty.

The game proceeds in several rounds, and in each round, the following events occur:

1. If there are no empty cells, the game ends. Otherwise, a number $i$ is chosen randomly from $1$ to $m$ with probability $p_i$, and an empty cell is chosen uniformly at random to be filled with $2^{i-1}$.
2. All numbers are shifted to the leftmost available positions while maintaining their relative order. For example, _ _ x _ y z becomes x y z _ _ _.
3. If there are no adjacent identical numbers, the round ends. Otherwise, the rightmost pair of identical adjacent numbers is replaced by their sum and an empty cell, and the score increases by the value of the sum. For example, x y y z _ _ becomes x 2y _ z _ _, and master pb gains $2y$ points. Then, the process returns to step 2.

Master pb wants to know: what is his expected total score?

Input

The first line contains two integers $n$ and $m$, representing the grid size and the range of the random numbers, respectively.

The second line contains $m$ integers, where the $i$-th number $a_i$ indicates that $p_i = \frac{a_i}{\sum_{j=1}^m a_j}$.

Output

Output a single integer representing the expected total score modulo $998244353$. Specifically, if the answer is the irreducible fraction $\frac{a}{b}$, you need to output $x$ such that $bx \equiv a \pmod{998244353}$.

Examples

Input 1

2 2
1 1

Output 1

2

Input 2

10 6
19 2 6 8 1 7

Output 2

5623384

Input 3

See attachment.

Constraints

For $1\%$ of the data, $1\leq n, m\leq 5$.

For $3\%$ of the data, $1\leq n, m\leq 300$.

For $7\%$ of the data, $1\leq n, m\leq 2000, 1\leq a_i\leq 100$.