Las vacas quieren formar una expedición para explorar el bosque al borde del territorio de Farmer John. Explorar requiere más habilidades que estar en el pasto comiendo hierba.
El equipo de $C$ vacas ($1 \le C \le 20$) numeradas 1..$C$ debe saber orientarse sin perderse, repeler grandes criaturas desagradables, contar chistes para mantener la moral, etc. Al menos una vaca debe poseer cada una de las $A$ habilidades especiales ($1 \le A \le 20$), numeradas 1..$A$. Algunas vacas tienen solo una, muchas varias, y otras son aprovechadas totalmente inútiles.
Dadas las vacas y sus habilidades, calcula cuántos equipos distintos pueden formar que en conjunto posean todas las habilidades.
Entrada
- Línea 1: los enteros $C$ y $A$.
- Líneas 2..$A$+1: cada línea describe una habilidad con enteros separados por espacios. La línea 2 describe la habilidad 1, la 3 la habilidad 2, etc. El primer entero $K$ ($1 \le K \le C$) es el número de vacas con ella. Los siguientes $K$ enteros indican esas vacas.
Salida
- Línea 1: un entero, el número de equipos de exploración distintos posibles.
Ejemplos
Entrada 1
4 2 2 3 1 1 2
Salida 1
6
Nota
Detalles de la entrada
Hay 4 vacas y 2 habilidades. Las vacas 1 y 3 tienen la habilidad 1, y solo la vaca 2 la habilidad 2. La vaca 4 tiene poco talento.
Detalles de la salida
Los equipos posibles son $\{1, 2\}$, $\{2, 3\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{2, 3, 4\}$ y $\{1, 2, 3, 4\}$.
Autor del problema: Percy Liang, 2004