Rozważmy kwadratowe miasto o rozmiarze $k \times k$. W każdej komórce znajduje się dokładnie jeden dom.

Ludzie mogą przemieszczać się z dowolnej komórki do sąsiedniej (tylko bokami) w czasie $1$.

Rząd postanowił wybudować $n$ szybkich mostów, aby usprawnić miasto. Każdy szybki most łączy dwie komórki $(x_1, y_1)$ oraz $(x_2, y_2)$ takie, że $x_1 \neq x_2$ oraz $y_1 \neq y_2$. Ludzie mogą przemieścić się z jednego końca mostu na drugi w czasie $|x_1 - x_2| + |y_1 - y_2| - 1$.

Aby przeanalizować, jak miasto stało się szybsze, należy obliczyć sumę najkrótszych odległości między wszystkimi parami komórek. Ponieważ wynik może być duży, należy go obliczyć modulo $998\,244\,353$.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $n, k$ ($0 \le n \le 500$, $2 \le k \le 10^9$) — liczba mostów oraz rozmiar miasta.

Każda z kolejnych $n$ linii zawiera cztery liczby całkowite $x_1, y_1, x_2, y_2$ ($1 \le x_1 < x_2 \le k$, $1 \le y_1, y_2 \le k$, $y_1 \neq y_2$). Gwarantuje się, że wszystkie krotki $(x_1, y_1, x_2, y_2)$ są różne.

Wyjście

Wypisz jedną liczbę całkowitą — odpowiedź na zadanie.

Przykład

Wejście 1

2 2
1 1 2 2
1 2 2 1

Wyjście 1

6

Wejście 2

0 1000000000

Wyjście 2

916520226

Wejście 3

5 5
1 1 3 3
3 3 5 1
3 3 4 5
3 3 5 4
1 5 3 3

Wyjście 3

946

Uwagi

W pierwszym przykładzie najkrótsza odległość między wszystkimi parami komórek wynosi $1$, więc suma wynosi $6$.