你在玩一个抽卡游戏。 这个游戏有 $n+1$ 种级别的抽卡方式,编号为 $0,1,\cdots,n$ 。抽出来的每张卡的等级是 $[0,m]$ 中的一个整数。 一次 0 级抽卡就是只抽一次卡,而一次 $i$ 级抽卡 $(1\le i\le n)$ 会包含 $b_i$ 次 $i-1$ 级抽卡,并且这次 $i$ 级抽卡**合法**当且仅当它包含的所有 $i-1$ 级抽卡合法,且抽出来的卡中至少有一张的等级大于等于 $i$ 。 对于每次 0 级抽卡,抽出一张等级为 $j$ 的卡的概率是 $\dfrac{a_j}{\sum_{k=0}^m a_k}$ 。 设 $p_j$ 表示在一次**合法**的 $n$ 级抽卡中抽出等级为 $j$ 的卡的期望次数,$q$ 表示一次 $n$ 级抽卡合法的概率。你需要对于 $0\le j\le m$ 求出 $(p_j\cdot q)\bmod {998244353}$ 。 ### 输入格式 第一行,两个正整数 $m,n$ 。 第二行, $m+1$ 个正整数 $a_0,a_1,\cdots,a_m$ 。 第三行, $n$ 个正整数 $b_1,b_2,\cdots,b_n$ 。 ### 输出格式 输出 $m+1$ 行,第 $j$ 行一个整数 $(p_{j-1}\cdot q)\bmod {998244353}$ 。 ### 样例一 #### input ``` 2 1 1 1 1 3 ``` #### output ``` 554580197 1 1 ``` #### explanation 共有 $27$ 种 $n$ 级抽卡,每种的可能性相等,且其中 $26$ 种是合法的。 $\frac 8 9 = 554580197 \pmod{998244353}$ ### 样例二 #### input ``` 3 2 1 1 2 1 2 3 ``` #### output ``` 58137752 260406016 517809313 758026833 ``` ### 样例三 #### input ``` 7 5 1 2 3 4 5 6 7 8 2 3 4 5 6 ``` #### output ``` 853156597 693809475 552532484 320522442 504282215 597794834 31931071 464311661 ``` ### 数据范围与提示 本题共 $20$ 组测试点,各 $5$ 分。 对于所有数据,$1\le n\le m\le 4000,1\le a_i\le 4000,2\le b_i\le 4000$ 。保证 $a_i,b_i$ 在范围内均匀随机。 | 测试点编号 | $m\le $ | 特殊限制 | | :---------: | :-----: | :-----------------------: | | $1\sim 3$ | $3$ | $\prod_{i=1}^n b_i\le 12$ | | $4\sim 6$ | $10$ | $b_i\le 3$ | | $7\sim 10$ | $50$ | $a_i\le 10$ | | $11\sim 15$ | $400$ | 无 .h=2 | | $16\sim 20$ | $ $ | | **时间限制:$\texttt{5s}$** **空间限制:$\texttt{512MB}$**