#P4734. 如何优雅地求和

    ID: 3854 传统题 2000ms 512MiB 尝试: 107 已通过: 68 难度: 8 上传者: 标签>CF2500省选/NOI-二项式反演卷积转化NTT阶乘逆元预处理二项式定理

如何优雅地求和

[清华集训2016] 如何优雅地求和

题目描述

有一个多项式函数 f(x)f(x),最高次幂为 xmx^m,定义变换 QQ:

Q(f,n,x)=∑k=0nf(k)(nk)xk(1−x)n−kQ(f,n,x)=∑_{k=0}^{n}f(k)\binom nkx^k(1−x)^{n−k}

现在给定函数 ff 和 n,xn,x,求 Q(f,n,x) mod 998244353Q(f,n,x)\bmod998244353。

出于某种原因,函数 ff 由点值形式给出,即给定 a0,a1,⋯,ama_0,a_1,⋯,a_m 共 m+1m+1 个数,f(x)=axf(x)=a_x。可以证明该函数唯一。

输入格式

第一行三个整数 n,m,xn,m,x,意义如前所述。

第二行共 m+1m+1 个整数,表示 a0,a1,⋯,ama_0,a_1,⋯,a_m。

输出格式

输出一行一个数表示答案,请对 998,244,353998,244,353 取模。

样例 #1

样例输入 #1

4 1 332748118
0 1

样例输出 #1

332748119

样例 #2

样例输入 #2

4 3 12
0 1 8 27

样例输出 #2

46704

提示

样例 22 解释

经计算得 f(x)=x3f(x)=x^3。

数据范围

对于所有的测试点,保证 1≤n≤1091≤n≤10^9,1≤m≤2×1041≤m≤2×10^4,0≤ai,x<998,244,3530≤a_i,x<998,244,353。