Problem Background

This is a template problem.

Problem Description

As known from elementary school knowledge, $n$ points $(x_i, y_i)$ can uniquely determine a polynomial $y = f(x)$.

Given these $n$ points, please determine this polynomial and compute the value of $f(k) \bmod 998244353$.

Input Format

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

The next $n$ lines, each containing two integers $x_i$ and $y_i$.

Output Format

A single line containing an integer, representing the value of $f(k) \bmod 998244353$.

Sample Input and Output

Sample Input #1

3 100
1 4
2 9
3 16

Sample Output #1

10201

Sample Input #2

3 100
1 1
2 2
3 3

Sample Output #2

100

Notes

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

$1 \leq n \leq 2 \times 10^3$, $1 \leq x_i, y_i, k < 998244353$, $x_i$ are pairwise distinct.

见题面 Input 部分

见题面 Output 部分