P4781 [Template] Lagrange Interpolation

This is a template problem.

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$.

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 one integer in one line, representing the value of $f(k) \bmod 998244353$.

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