【模板】拉格朗日插值

题目背景

这是一道模板题

题目描述

~~由小学知识可知~~ $n$ 个点 $(x_i,y_i)$ 可以唯一地确定一个多项式 $y = f(x)$。 现在,给定这 $n$ 个点,请你确定这个多项式,并求出 $f(k) \bmod 998244353$ 的值。

输入输出格式

输入格式


第一行两个整数 $n,k$。 接下来 $n$ 行,第 $i$ 行两个整数 $x_i,y_i$。

输出格式


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

输入输出样例

输入样例 #1

3 100
1 4
2 9
3 16

输出样例 #1

10201

输入样例 #2

3 100
1 1
2 2
3 3

输出样例 #2

100

说明

样例一中的多项式为 $f(x)=x^2+2x+1$,$f(100) = 10201$。 样例二中的多项式为 $f(x)=x$,$f(100) = 100$。 --- $1 \le n \leq 2\times 10^3$,$1 \le x_i,y_i,k < 998244353$,$x_i$ 两两不同。