Background

This is a template problem.

Problem Description

For $n$ points $(x_i, y_i)$, if $\forall i \neq j, x_i \neq x_j$, then these $n$ points uniquely determine a polynomial $y = f(x)$ of degree $n - 1$.

Now, given such $n$ points, please determine this degree $n - 1$ polynomial and compute the value of $f(k) \bmod 998244353$.

Input Format

The first line contains two integers $n, k$.

The next $n$ lines each contain two integers $x_i, y_i$ on the $i$-th line.

Output Format

Output one integer in one line, representing the value of $f(k) \bmod 998244353$.

3 100
1 4
2 9
3 16

10201

3 100
1 1
2 2
3 3

100

Hint

In Sample 1, the polynomial is $f(x) = x^2 + 2x + 1$, and $f(100) = 10201$.

In Sample 2, the polynomial is $f(x) = x$, and $f(100) = 100$.

Constraints: $1 \le n \le 2 \times 10^3$, $1 \le x_i, y_i, k < 998244353$, and all $x_i$ are pairwise distinct.

Translated by ChatGPT 5