题目描述

有一个多项式函数 $f(x)$，最高次幂为 $x^m$，定义变换 $Q$：

现在给定函数 $f$ 和 $n,x$，求 $Q(f,n,x)\bmod998244353$。

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

输入格式

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

第二行共 $m+1$ 个整数，表示 $a_0,a_1,⋯,a_m$。

输出格式

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

4 1 332748118
0 1

332748119

4 3 12
0 1 8 27

46704

提示

样例 $2$ 解释

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

数据范围

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