As vacas querem formar uma expedição para explorar o bosque na extremidade do território de Farmer John. Explorar exige mais competências do que ficar no pasto a comer erva.
A equipa de $C$ vacas ($1 \le C \le 20$) numeradas 1..$C$ deve saber orientar-se sem se perder, afastar grandes criaturas desagradáveis, contar piadas para manter o ânimo, etc. Pelo menos uma vaca deve possuir cada uma das $A$ capacidades especiais ($1 \le A \le 20$), numeradas 1..$A$. Algumas têm só uma, muitas várias, e outras são aproveitadoras completamente inúteis.
Dadas as vacas e as capacidades de cada uma, calcule o número de equipas distintas que, no conjunto, possuem todas as capacidades.
Entrada
- Linha 1: os inteiros $C$ e $A$.
- Linhas 2..$A$+1: cada linha descreve uma capacidade com inteiros separados por espaços. A linha 2 descreve a capacidade 1, a 3 a capacidade 2, etc. O primeiro inteiro $K$ ($1 \le K \le C$) é o número de vacas com ela. Os $K$ inteiros seguintes indicam essas vacas.
Saída
- Linha 1: um inteiro, o número de equipas de exploração distintas possíveis.
Exemplos
Entrada 1
4 2 2 3 1 1 2
Saída 1
6
Nota
Detalhes da entrada
Há 4 vacas e 2 capacidades. As vacas 1 e 3 têm a capacidade 1, e só a vaca 2 a capacidade 2. A vaca 4 tem pouco talento.
Detalhes da saída
As equipas possíveis são $\{1, 2\}$, $\{2, 3\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{2, 3, 4\}$ e $\{1, 2, 3, 4\}$.
Autor do problema: Percy Liang, 2004