Існує \(M\) множин, які називаються \(S_1 ​,S_2 ​ ,…,S_M ​ \)​ і складаються з цілих чисел від 1 до \(N\). \(S_i\) ​ складається з \(C_i\) ​ цілих чисел \(a_{i,1} ​,a_{i,2} ​,…,a_{i, C_i} \)​.

Існує \((2^M −1)\) способів вибрати один або більше наборів із \(M\) множин.

Скільки з них задовольняють наступну умову?

• Для всіх цілих чисел \(x\) таких, що \(1≤x≤N\), існує принаймні один вибраний набір, що містить \(x\).

Обмеження

• \(1≤N≤10\)
• \(1≤M≤10\)
• \(1≤C_i ​ ≤N\)
• \(1≤a_{i,1} ​ <a_{i,2} ​ <⋯<a_{i,C_i} ​ ≤N\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N,M\).

Далі ідуть \(M\) блоків у такому форматі.

Перший рядок блоку містить ціле число \(C_i\) \((1 \le i \le M\))

Наступний   рядок блоку містить цілі числа \(a_{i,j]\) \((1 \le j \le C_i\)).

Формат вихідних даних

У вихідний потік виведіть кількість способів вибору множин, які задовольняють умови в постановці задачі.

Приклад вхідних даних

3 3
2
1 2
2
1 3
1
2

Приклад вихідних даних

3

Набори, надані у вхідних даних, є \(S_1\) ​ ={1,2},\(S_2\) ​ ={1,3},\(S_3\) ​ ={2}.

Наступні три способи задовольняють умови в постановці задачі:

• вибір \(S_1 ​, S_2\) ​ ;
• вибір \(S_1 , S_2 , S_3\) ;
• вибираючи \(S_2 , S_3 \).

Приклад вхідних даних

4 2
2
1 2
2
1 3

Приклад вихідних даних

0

Приклад вхідних даних

6 6
3
2 3 6
3
2 4 6
2
3 6
3
1 5 6
3
1 3 6
2
1 4

Приклад вихідних даних

18