Le mucche vogliono formare una spedizione per esplorare il bosco ai margini del territorio di Farmer John. Esplorare richiede più abilità che stare al pascolo a mangiare erba.
La squadra di $C$ mucche ($1 \le C \le 20$) numerate 1..$C$ deve sapersi orientare senza perdersi, respingere grandi creature cattive, raccontare barzellette per tenere alto il morale, ecc. Almeno una mucca deve possedere ciascuna delle $A$ abilità speciali ($1 \le A \le 20$), numerate 1..$A$. Alcune ne hanno una sola, molte diverse, altre sono approfittatrici completamente inutili.
Date le mucche e le loro abilità, calcola il numero di squadre distinte che nel complesso possiedono tutte le abilità.
Input
- Riga 1: gli interi $C$ e $A$.
- Righe 2..$A$+1: ogni riga descrive un’abilità con interi separati da spazi. La riga 2 descrive l’abilità 1, la 3 l’abilità 2, ecc. Il primo intero $K$ ($1 \le K \le C$) è il numero di mucche con essa. I successivi $K$ interi indicano queste mucche.
Output
- Riga 1: un intero, il numero di squadre di esplorazione distinte possibili.
Esempi
Input 1
4 2 2 3 1 1 2
Output 1
6
Nota
Dettagli dell’input
Ci sono 4 mucche e 2 abilità. Le mucche 1 e 3 hanno l’abilità 1, solo la mucca 2 l’abilità 2. La mucca 4 ha poco talento.
Dettagli dell’output
Le squadre possibili sono $\{1, 2\}$, $\{2, 3\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{2, 3, 4\}$ e $\{1, 2, 3, 4\}$.
Autore del problema: Percy Liang, 2004