题目描述

You are given $N$ distinct points on a 2D plane. The $i$-th point is located at $(x_i, y_i)$.

For each integer $k \geq 1$, let $f(k)$ be the maximum number of non-degenerate triangles you can place under the following conditions:

• You add $k$ new points on the plane such that all $N + k$ points are distinct.
• Each triangle has its vertices among the $N + k$ points.
• No two triangles have an intersection with a positive area.

Compute $\left(\sum \limits_{k=1}^{K} f(k)\right) \mod 998244353$.

输入格式

The input consists of a single test case in the following format.

$$\begin{aligned} & N \ K \\ & x_1 \ y_1 \\ & \vdots \\ & x_N \ y_N \end{aligned} $$

The first line contains two integers $N$ and $K$ ($1 \leq N \leq 200\,000$, $1 \leq K \leq 10^9$), representing the number of points and the maximum value of $k$. Each of the next $N$ lines contains two integers $x_i$ and $y_i$ ($0 \leq x_i, y_i \leq 10^9$), representing the coordinates of the $i$-th point. It is guaranteed that all $N$ points are distinct.

输出格式

Print the answer.

5 1
0 0
0 20
20 20
20 0
10 10

6

5 20250914
0 0
0 100
20 25
9 14
50 0

894241420