ksiruri

Se consideră un număr natural $K$ și o secvență de $N$ șiruri $s_1$, $s_2$, $\dots$, $s_N$. Fiecare șir este format din cifre distincte. Pentru două șiruri $s_i$ și $s_j$ se definește operația de scădere (–) astfel: $s_i - s_j$ va conține doar șirul de cifre care apar în $s_i$, dar nu apar în $s_j$. De exemplu, dacă $s_i = (1, 3, 8)$ și $s_j = (2, 9, 3)$, atunci $s_i - s_j = (1, 8)$. Această operație nu este asociativă, $(s_i - s_j) - s_p$ este diferită de $s_i - (s_j - s_p)$.

De aceea, dacă se alege un subșir $s_{i_1}$, $s_{i_2}$, $\dots$, $s_{i_p}$ din secvență, atunci convenim ca $s_{i_1} - s_{i-2} - \dots - s_{i_p}$ să se execute de la dreapta la stânga.

Exemplu: $(1, 2, 3) - (2, 3) - (1, 3) = (1, 2, 3) - (2) = (1, 3)$. S-au obținut două cifre distincte.

Cerinţă

Să se determine numărul subșirurilor nevide $s_{i_1}$, $s_{i_2}$, $\dots$, $s_{i_p}$ din secvența $s_1$, $s_2$, $\dots$, $s_N$ asupra cărora, dacă se efectuează operația de scădere (adică $s_{i_1}$ - $s_{i_2}$ - $\dots$ - $s_{i_p}$), se obțin cel puțin $K$ cifre distincte. Pentru că numărul subșirurilor poate fi foarte mare, atunci el se va calcula modulo $123 \ 457$.

Date de intrare

Fişierul ksiruri.in conţine pe prima linie numerele naturale $K$ și $N$. Pe următoarele $N$ linii se află câte un șir $s_i$. Linia $i+1$, $i = 1 \dots N$, va conține valorile $m \ c_1 \ c_2 \dots$ cm, unde $m$ este numărul de termeni al șirului $s_i$, iar $c_1$, $c_2$, $\dots$, cm sunt cifrele distincte ale șirului $s_i$.

Date de ieșire

Fişierul ksiruri.out conţine un singur număr natural reprezentând numărul de subșiruri, modulo $123 \ 457$.

Restricții și precizări

• $1 \leq K \leq 8$
• $2 \leq N \leq 50 \ 000$
• $1 \leq i_1 < i_2 < \dots < i_p \leq N$

Exemplu

ksiruri.in

3 3
5 5 6 7 8 9
3 4 5 6
3 7 8 9 

ksiruri.out

6

Explicație

$s_1$ = $5 \ 6 \ 7 \ 8 \ 9$
$s_2$ = $4 \ 5 \ 6$
$s_3$ = $7 \ 8 \ 9$

Cele șase subșiruri nevide sunt: $s_1$, $s_1-s_2$, $s_1-s_2-s_3$, $s_2$, $s_2-s_3$, $s_3$