【模板】拉格朗日插值

题目背景

这是一道模板题

题目描述

由~~小学知识~~可知,$n$个点$(x_i,y_i)$可以唯一地确定一个多项式 现在,给定$n$个点,请你确定这个多项式,并将$k$代入求值 求出的值对$998244353$取模

输入输出格式

输入格式


第一行两个正整数$n,k$,含义如题 接下来$n$行,每行两个正整数$x_i,y_i$,含义如题

输出格式


一个整数表示答案

输入输出样例

输入样例 #1

3 100
1 4
2 9
3 16

输出样例 #1

10201

输入样例 #2

3 100
1 1
2 2
3 3

输出样例 #2

100

说明

$n \leq 2000 \; \; \; x_i,y_i,k \leq 998244353$ 样例一中的三个点确定的多项式是$f(x)=x^2+2x+1$,将$100$代入求值得到$10201$ 样例二中的三个点确定的多项式是$f(x)=x$,将$100$代入求值得到$100$ 如果你不会拉格朗日插值,你可以到[这里](http://www.ebola.pro/article/notes/Lagrange)去学习一下 **此外,请注意算法的常数问题,建议开启O2优化**