[AdditionalFile2504.zip](file://AdditionalFile2504.zip?type=additional_file)

#2504. 「2018 集训队互测 Day 5」小 H 爱染色

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

有排成一列的 $n$ 个球，编号依次为 $0$ 到 $n-1$ ，初始都为白色。小 $H$ 会重复以下操作共 $2$ 次：随机选择其中的 $m$ 个球将它们染成黑色（可以重复染黑球）。小 $H$ 对编号最小的黑球情有独钟，她想知道，如果令 $A$ 为它的编号， $F(A)$ 的期望是多少。其中， $F(x)$ 为一个次数不超过 $m$ 的多项式， $F(A)$ 表示 $x=A$ 时多项式的值。

输入格式

第一行两个整数 $n,m$ 。
第二行 $m+1$ 个整数，第 $i$ 个整数为 $F(i-1)$ 。

输出格式

一行一个整数，如果令 $E$ 表示 $F(A)$ 的期望，输出 $E\times {\binom{n}{m}}^2$ 模 $998244353$ 的值。

样例

输入

8 5
45856608 386378255 106492167 28766400 272276589 93721672

输出

321347828

数据范围与提示

• 对于 $10\%$ 的数据，$n \leq 10$，$m \leq 5$
• 对于 $20\%$ 的数据，$n \leq 100$，$m \leq 100$
• 对于 $30\%$ 的数据，$n \leq 1000$，$m \leq 1000$
• 对于另外 $5\%$ 的数据，$m \leq 1000000$，且保证多项式 $F(x)=1$
• 对于另外 $5\%$ 的数据，$m \leq 5000$，且保证多项式 $F(x)=x$
• 对于另外 $10\%$ 的数据，$m \leq 5000$，且保证多项式 $F(x)=x^m$
• 对于 $70\%$ 的数据，$m \leq 5000$
• 对于 $80\%$ 的数据，$m \leq 20000$
• 对于 $100\%$ 的数据，$n \leq 998244353$，$m \leq 1000000$