Perfect Isolation

filename: isolation.c, CPU Time limit: 5 seconds

Spoločnosť Krásne a parádne izolácie (KPI) sa pokúša analyzovať vlastnosti jej najnovšej série 2018 pre izolovanie stropov s názvom PROG. Izolácia PROG pozostáva z n vrstiev izolačného materiálu, kde každý z nich má inú hodnotu tepelného odporu (udávaný ako kladné celé číslo). Analýza KPI spočíva v tom, že všetky hodnoty tepelného odporu danej izolácie uloží do podoby binárneho vyhľadávacieho stromu. Následne sa overí, či neexistuje korelácia medzi tvarom vytvoreného binárneho vyhľadávacieho stromu a kvalitou celej stavby.

Pre dosiahnutie požadovaných výsledkov, KPI vezme zoznam hodnôt tepelných odporov usporiadaných od najvrchnejšej vrstvy po najspodnejšiu a vloží ich jeden po druhom do binárneho vyhľadávacieho stromu. Pravidlá pre vloženie hodnoty v do stromu sú nasledovné:

• Ak je strom prázdny, v sa stane jeho koreňom.
• Ak strom nie je prázdny, porovnaj v s hodnotou koreňa stromu. Ak je v menšie, vlož ho do ľavého podstromu. V opačnom prípade vlož v do pravého podstromu.

Spoločnosť KPI má k dispozícii niekoľko prototypov. Potrebuje zistiť, ktoré skupiny izolácií majú rovnaký tvar výsledného stromu a analyzovať ich spoločne.

Príklad:

Predpokladajme, že spoločnosť KPI má k dispozícii 5 prototypov pre stropnú izoláciu a každý z nich má 3 vrstvy (viď ukážkový vstup 1 a obrázok 1). Vrchná vrstva prvého prototypu má hodnotu tepelného odporu 3, stredná vrstva 8 a spodná vrstva 2. Hodnoty tepelného odporu druhej vrstvy sú 4, 2 a 5. Všimnite si, že tvar stromov týchto dvoch prototypov je rovnaká, takže ich bude KPI analyzovať spolu.

Vzhľadom na množinu prototypov je vašou úlohou zistiť, koľko rozličných tvarov stromov obsahujú.

Vstup

Prvý riadok vstupu obsahuje dve celé čísla - číslo n (1 <= n <= 50) udáva počet prototypov pre izolovanie stropov k analýze, a číslo k (1 <= k <= 20) udáva počet vrstiev každého prototypu.

Nasledujúcich n riadkov opisuje jednotlivé prototypy. Každy riadok obsahuje k rozličných celých čísiel (v rozsahu od 1 do 10^6 vrátane), ktoré reprezentujú hodnoty tepelných odporov vrstiev prototypu zoradených od najvrchnejšej po najspodnejšiu vrstvu.

Výstup

Počet rozličných tvarov stromov.

Ukážkový vstup a výstup 1

5 3
3 8 2
4 2 5
2 6 10
3 7 6
10 8 4

4

Ukážkový vstup a výstup 2

3 4
4 2 3 10000
4 5 3 2
34 43 18 24

2