#P4781. 【模板】拉格朗日插值

【模板】拉格朗日插值

题目背景

这是一道模板题

题目描述

由小学知识可知 nn 个点 (xi,yi)(x_i,y_i) 可以唯一地确定一个多项式 y=f(x)y = f(x)

现在,给定这 nn 个点,请你确定这个多项式,并求出 f(k)mod998244353f(k) \bmod 998244353 的值。

输入格式

第一行两个整数 n,kn,k

接下来 nn 行,第 ii 行两个整数 xi,yix_i,y_i

输出格式

一行一个整数,表示 f(k)mod998244353f(k) \bmod 998244353 的值。

3 100
1 4
2 9
3 16
10201
3 100
1 1
2 2
3 3
100

提示

样例一中的多项式为 f(x)=x2+2x+1f(x)=x^2+2x+1f(100)=10201f(100) = 10201

样例二中的多项式为 f(x)=xf(x)=xf(100)=100f(100) = 100


1n2×1031 \le n \leq 2\times 10^31xi,yi,k<9982443531 \le x_i,y_i,k < 998244353xix_i 两两不同。