Stack

题目描述

Given integers $n$, $k$, and a sequence $p_{1 \dots k}$.

There is a stack, initially empty. Perform the following insertion operation $n$ times:

1. Randomly choose an integer $v$ from $[1,k]$, where the probability of $v=x$ is $\frac{p_x}{\sum_{i=1}^k p_i}$.
2. If the top of the stack is exactly $v$, pop it, then set $v \gets v+1$. Repeat this step until the top of the stack differs from $v$.
3. Push $v$ onto the stack.

Find the expected number of elements in the stack after $n$ insertions, modulo $M=998244353$.

In other words, the expected value can be written as $\frac{P}{Q}$ ($\gcd(P,Q)=1$). You need to find the unique integer $R \in [0,M-1]$ such that $R \cdot Q \equiv P \pmod M$.

输入格式

The first line of input contains two integers $n$ and $k$. The second line contains $k$ integers, namely $p_{1},p_2,\dots,p_k$.

输出格式

The output should contain a single line with one integer: the expected value you computed.

样例输入 #1

3 2
1 2

样例输出 #1

961272342

样例输入 #2

3 3
1 2 1

样例输出 #2

779878403

样例输入 #3

6 10
3293122 304483210 0 920851348 548604332 397404204 78439209 998244352 439820043 291380245

样例输出 #3

168058624