Description

Note: This problem does not consider special turning methods such as “maze”, teleport lines such as “football”, or jumping and landing such as “piano”.

As everyone knows, the path in Dancing Line is a polyline. Each click will make the moving direction rotate $90^\circ$ clockwise or counterclockwise, and the rotation directions of any two adjacent rotations are different.

For example, the following are valid paths (the path does not have to follow the grid of the Cartesian coordinate system):

And the following are invalid paths:

The rotation angle is not $90^\circ$:

Turning left twice in a row:

A path that obviously does not meet the requirements:

k Tian placed the path into a 2D coordinate system and wrote down the coordinates of the path’s start point, end point, and turning points (both coordinates are integers). He put them into a file and left.

When k Tian came back and turned on his computer, he found that all the data in his file was messed up. The coordinates of the points were no longer stored in the original order, but were arranged in a strange order.

k Tian wants to reconstruct the path from these data. He also wants to estimate the difficulty of this level, denoted by $s$:

$$s=\sum\limits_{i=1}^{n}{t_i^2},t_i=\dfrac{d(P_{i-1},P_i)}{v}$$

Where:

• $P_i(0\leq i\leq n)$ denotes the $i$-th point of the reconstructed path starting from the start point (the start point is $P_0$, and the end point is $P_n$).
• $v$ is the line speed, a given positive integer.
• $d(A,B)$ denotes the distance between points $A$ and $B$ in the coordinate system.

Can you help him?

Input Format

The first line contains two positive integers $n,v$, with meanings as described above.

The next $n+1$ lines each contain two integers, representing the coordinates of each point in the file before reconstruction.

Output Format

Output one number $s$ as described above, and output its value modulo $998244353$.

More specifically, suppose $s$ in lowest terms is $\dfrac{x}{y}$. You need to output the smallest non-negative integer satisfying $ys\equiv x\pmod{998244353}$. In this problem, you should output $x\times y^{998244351}\bmod 998244353$.

8 2
-7 7
-11 5
-3 4
-5 3
4 0
0 -2
5 -2
13 2
15 -2

249561142

Hint

Explanation of the samples

For Sample 1, the path is as follows:

The lengths of the segments are $2\sqrt{5},2\sqrt{5},\sqrt{5},3\sqrt{5},2\sqrt{5},\sqrt{5},4\sqrt{5},2\sqrt{5}$. The value of $s$ is $53\dfrac{3}{4}$, and the result after taking modulo is $249561142$.

---

Constraints and Notes

This problem uses bundled tests.

• Subtask 1 (5 pts): $n\leq 6$.
• Subtask 2 (15 pts): $n\leq 80$.
• Subtask 3 (30 pts): $n\leq 800$.
• Subtask 4 (50 pts): no special constraints.

For $100\%$ of the testdata, it holds that:

• $2\leq n \leq 10^6$.
• $-10^9\leq x_i,y_i\leq 10^9$.
• $1\leq v\leq 10^7$.
• All point coordinates are guaranteed to be pairwise distinct.
• The given points are guaranteed to be able to reconstruct one and only one unique path.

---

$d(A,B)=\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}$, where $A(x_A,y_A),B(x_B,y_B)$.

---

Source: JROI-2 Summer Fun Round - T3

Idea&Sol&Data: kkk's little simp

Std&Retest: Tony2

Translated by ChatGPT 5