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

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有排成一列的 nnn 个球,编号依次为 000n−1n-1n1 ,初始都为白色。小 HHH 会重复以下操作共 222 次:随机选择其中的 mmm 个球将它们染成黑色(可以重复染黑球)。小H对编号最小的黑球情有独钟,她想知道,如果令 AAA 为它的编号, F(A)F(A)F(A) 的期望是多少。其中, F(x)F(x)F(x) 为一个次数不超过 mmm 的多项式, F(A)F(A)F(A) 表示 x=Ax=Ax=A 时多项式的值。

输入格式

第一行两个整数 n,mn,mn,m
第二行 m+1m+1m+1 个整数,第 iii 个整数为 F(i−1)F(i-1)F(i1)

输出格式

一行一个整数,如果令 EEE 表示 F(A)F(A)F(A) 的期望,输出 E×Cnm×CnmE\times C^{m}_{n}\times C^{m}_{n}E×Cnm×Cnm998244353998244353998244353 的值。

样例

样例输入

8 5  
45856608 386378255 106492167 28766400 272276589 93721672

样例输出

321347828

数据范围与提示

  • 对于10%10\%10%的数据, n≤10n \leq 10n10m≤5m \leq 5m5
  • 对于20%20\%20%的数据, n≤100n \leq 100n100m≤100m \leq 100m100
  • 对于30%30\%30%的数据, n≤1000n \leq 1000n1000m≤1000m \leq 1000m1000
  • 对于另外5%5\%5%的数据, m≤1000000m \leq 1000000m1000000 ,且保证多项式F(x)=1F(x)=1F(x)=1
  • 对于另外5%5\%5%的数据, m≤5000m \leq 5000m5000 ,且保证多项式F(x)=xF(x)=xF(x)=x
  • 对于另外10%10\%10%的数据, m≤5000m \leq 5000m5000 ,且保证多项式F(x)=xmF(x)=x^mF(x)=xm
  • 对于70%70\%70%的数据, m≤5000m \leq 5000m5000
  • 对于80%80\%80%的数据, m≤20000m \leq 20000m20000
  • 对于100%100\%100%的数据, n≤998244353n \leq 998244353n998244353m≤1000000m \leq 1000000m1000000