181045 / 克洛涅的多项式

题号：NC25113
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

克洛涅修女来到了这所孤儿院。Sister 很快就和大家打成一片，开始了捉迷藏的游戏。

Sister 今天藏起来了一个 n 次的多项式 F(x)。同时，作为线索，她给出了一个 m 次的多项式 G(x) 。这里 m < n 。她又给出了一个有恰好 n 个不同元素的集合 S 。Sister 说，她藏起来的多项式满足两个性质：

1. 最高次项系数为 1 。

2. 对于所有 S 中的元素 x ，都有 F(x) = G(x) 。即， $\forall x \in S, F(x)=G(x)$ 。

有了这些线索和条件， Sister 藏起来的多项式就可以被唯一确定了。诺曼心中已有了答案。那么，你能不能找得比诺曼更快呢？

为了方便，你只需要回答将 x=k 代入 Sister 的多项式后的值除以 998244353 后的余数即可。也就是 $F(k) \bmod 998244353$ 的值。

由于读入文件较大，请使用较快的读入方式。

这里给出一个 C++ 的快速读入板子：

namespace io {
const int SIZE = 1e7 + 10;
char inbuff[SIZE];
char *l, *r;
inline void init() {
l = inbuff;
r = inbuff + fread(inbuff, 1, SIZE, stdin);
}
inline char gc() {
if (l == r) init();
return (l != r) ? *(l++) : EOF;
}
void read(int &x) {
x = 0; char ch = gc();
while(!isdigit(ch)) ch = gc();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
}
} using io::read;

在主程序中 read(x); 即可。

输入描述:

输入的第一行包含三个整数 n, m, k ，意义如题面所述。
第二行包含 n 个整数，表示所给出集合中的元素。保证集合中元素互不相同。
第三行包含 m+1 个整数，表示所给多项式 G(x) 的各项系数。这一行中第  个数字表示 G(x) 中  次项的系数。

输出描述:

输出仅一行，一个整数表示 F(k) 的值在模 998244353 意义下的结果。

示例1

输入

复制

3 2 3
0 1 2
1 1 1

输出

复制

说明

Sister 给出的多项式 G(x) 为  。集合 S 为 {0, 1, 2} ，故 F(0) = G(0) = 1, F(1) = G(1) = 3, F(2) = G(2) = 7 。所以 F(x) 为  。答案为F(3) = 19 。

备注:


 多项式系数、S 中元素