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