La ora de geometrie, Aurel a primit de la profesorul X o temă foarte dificilă: fiind date N segmente orizontale (paralele cu axa Ox), cu extremităţile de coordonate numere naturale, să se numere câte dreptunghiuri speciale pot fi formate în plan, luând în considerare aceste segmente.

Un dreptunghi este special dacă respectă simultan următoarele trei condiţii:
1. Cele patru vârfuri ale dreptunghiului au coordonate numere naturale
2. Laturile dreptunghiului sunt paralele cu axa Ox, respectiv Oy
3. Fiecare dintre cele patru vârfuri ale dreptunghiului aparţine cel puţin unui segment

Cerinţa

Scrieţi un program care să-l ajute pe Aurel să determine numărul de posibilităţi de a plasa un dreptunghi în plan astfel încât să fie dreptunghi special. Deoarece rezultatul poate fi foarte mare, se va determina numărul modulo 946021 (restul împărţirii numărului calculat la 946021).

Date de intrare

Pe prima linie a fişierului de intrare drept.in se află numărul natural N reprezentând numărul de segmente orizontale. Pe următoarele N linii se află câte 3 numere naturale y x1 x2 reprezentând coordonatele segmentelor astfel: y – coordonata verticală (ordonata), x1 şi x2 – coordonatele orizontale (abscisele).

Date de ieşire

Fişierul de ieşire drept.out va conţine un singur număr, reprezentând restul împărţirii numărului total de dreptunghiuri speciale la 946021.

Restricţii şi precizări

• 1 ≤ N ≤ 50.000
• 0 ≤ x1≤ x2 ≤ 1.000.000.000
• 0 ≤ y ≤ 1000
• Vârfurile oricărui dreptunghi special sunt distincte două câte două şi nu pot avea toate aceeaşi ordonată
• Pentru un număr de teste în valoare de 60 de puncte, N ≤ 5000

Exemple

Exemplul 1

drept.in

3
2 2 3
1 1 4
3 3 4

drept.out

2

Exemplul 2

drept.in

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

drept.out

12