A. 小 H 爱染色

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

题目描述

有排成一列的 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 C^{m}_{n}\times C^{m}_{n} 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