Polynomial Interpolation

Given \(n\) points \( (x_i, y_i) \) with distinct x-coordinates (i.e. \(x_i \neq x_j \) for all \(i \neq j\)), there exists a unique polynomial \(f(x)\) of degree \(n-1\) that passes through all these points. In other words, the points uniquely determine a polynomial of the form \(y = f(x)\).

Your task is to compute \(f(k) \bmod 998244353\) for a given value \(k\) based on the provided points.

You can use the Lagrange interpolation formula which is given by:

\[ f(k) = \sum_{i=1}^{n} y_i \cdot \prod_{\substack{1 \leq j \leq n\\ j \neq i}} \frac{k - x_j}{x_i - x_j} \quad (\bmod\; 998244353) \]

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space.

The following \(n\) lines each contain two integers \(x_i\) and \(y_i\) separated by a space.

outputFormat

Output a single integer: \(f(k) \bmod 998244353\).

sample

2 5
1 2
3 8

14