8. Dežo

Dežo sa chce dostať zo sústredenia v Trnave domov do Nitry, aby mohol ísť na záchod. Rozhodol sa, že pôjde stopom. Teraz ho ale trápi jedna dôležitá otázka: “Koľko je ciest?”

Úloha

Hlavnú cestu medzi Trnavou a Nitrou si predstavte ako úsečku dlhú \(s\). Dostanete zoznam áut, ktoré idú po tejto ceste, pre každé z nich miesto kde sa pripojí a kde sa odpojí z hlavnej cesty a tiež čas, kedy sa pripojí. Všetky autá idú rovnakou rýchlosťou \(1\text{km}/\text{min}\) a rovnakým smerom.

Dežo sa v čase \(0\) nachádza v Trnave. Môže nastúpiť na ľubovoľné okoloidúce auto (aj presne v bode kde sa pripája) a kdekoľvek z neho vyskočiť (najneskôr v bode kde sa odpojí). V bode X vie presúpiť z jedného auta na druhé, iba ak to druhé príde do bodu X ostro neskôr ako prvé. Zároveň, ak sa Dežo vezie nejakým autom, musí sa viezť nenulový čas.

Zistite koľkými spôsobmi sa môže Dežo dostať do Nitry. Spôsoby sú rôzne, ak použije rôznu množinu áut (všimnite si poradie je jasne dané). Keďže výsledok môže byť veľký, vypíšte iba jeho zvyšok po delení \(10^9+7\).

Formát vstupu

V prvom riadku sú dve čísla \(n\), \(s\) - počet áuta a vzdialenosť medzi Trnavou a Nitrou. Nasleduje \(n\) riadkov popisujúcich autá. V \(i\)-tom z nich sú tri čísla \(a_i\), \(b_i\), \(t_i\) (\(0\leq a_i<b_i\leq s\), \(t_i \leq 10^9\)). Tie znamenajú, že \(i\)-te auto sa v čase \(t_i\) pripojí na cestu \(a_i\) kilometrov od Trnavy a odpojí sa v bode \(b_i\) kilometrov od Trnavy.

Formát výstupu

Vypíšte jedno číslo - počet možností, koľkými sa vie Dežo dostať do Nitry, modulo \(10^9+7\).

Hodnotenie

Je \(8\) sád po \(1\) bode. Platia v nich nasledujúce dodatočné obmedzenia:

Navyše v sadách \(4\) a \(6\) je zaručené, že sa nikdy nenachádzajú dve autá v tom istom bode.

Príklad

Input:

5 5
0 3 0 
0 2 1
1 3 5
3 5 9
2 5 6

Output:

10

Možné postupnosti áut sú \(14\), \(15\), \(154\), \(125\), \(1234\), \(1254\), \(134\), \(25\), \(254\) a \(234\).