505014 - 拉格朗日插值

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

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

Input

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

Output

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

Examples

Input

3 100
1 4
2 9
3 16

Output

10201

Input

3 100
1 1
2 2
3 3

Output

100
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题