505014 - 拉格朗日插值

【题目描述】拉格朗日插值(lagrange)

n 个点(xi,yi) 可以唯一地确定一个多项式y=f(x)。 现在,给定这n个点,请你确定这个多项式,并求出f(k) mod 998244353 的值。

输入

第一行两个整数n和k(1≤n≤2×10^3)。 接下来n行,第i行两个整数xi和yi(1≤xi,yi,k<998244353,xi两两不同)。

输出

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

样例

输入

3 100
1 4
2 9
3 16

输出

10201

输入

3 100
1 1
2 2
3 3

输出

100
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题