Considérons une ville carrée de taille $k \times k$. Il y a exactement une maison dans chaque cellule.

Les gens peuvent se déplacer d'une cellule à une cellule voisine (uniquement par les côtés) en 1 unité de temps.

Le gouvernement a décidé de construire $n$ ponts rapides pour améliorer la ville. Chaque pont rapide relie deux cellules $(x_1, y_1)$ et $(x_2, y_2)$ telles que $x_1 \neq x_2$ et $y_1 \neq y_2$. Les gens peuvent aller d'une extrémité du pont à l'autre en $|x_1 - x_2| + |y_1 - y_2| - 1$ unités de temps.

Pour analyser à quel point la ville est devenue plus rapide, vous devez calculer la somme des distances les plus courtes entre toutes les paires de cellules. Comme cette somme peut être grande, calculez-la modulo $998\,244\,353$.

Entrée

La première ligne contient deux entiers $n, k$ ($0 \le n \le 500$, $2 \le k \le 10^9$) — le nombre de ponts et la taille de la ville.

Chacune des $n$ lignes suivantes contient quatre entiers $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$). Il est garanti que tous les tuples $(x_1, y_1, x_2, y_2)$ sont différents.

Sortie

Affichez un seul entier — la réponse au problème.

Exemples

Entrée 1

2 2
1 1 2 2
1 2 2 1

Sortie 1

6

Remarque

Dans le premier exemple, la distance la plus courte entre toutes les paires de cellules est 1, donc la somme est 6.

Entrée 2

0 1000000000

Sortie 2

916520226

Entrée 3

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

Sortie 3

946