Xét tập \(S\) chứa các số nguyên từ \(1\) đến \(n\). Các tập con \(P = \{P_1, P_2, \dots, P_k\}\) được gọi là một cách phân chia tập \(S\) nếu \(S = \bigcup_{i=1}^{k} P_i\) và \(P_i \cap P_j = \emptyset\) với \(i \neq j\). Ví dụ, với \(n = 5\), một trong các cách phân chia là \(P_1 = \{1, 3\}, P_2 = \{2, 4, 5\}\).

Cách phân chia \(P\) gọi là tránh được tập \(Q\) nếu không có tập \(P_i\) nào chứa \(Q\) như một tập con. Ví dụ, cách phân chia trên tránh được tập \(\{1, 2\}\) và \(\{3, 4\}\), nhưng không tránh được \(\{1, 3\}\) hoặc \(\{2\}\).

Yêu cầu: Cho \(n\) và các tập \(Q_1, Q_2, \dots, Q_m\). Hãy xác định số các phân chia \(S\) tránh được các tập \(Q_i, i = 1 \div m\).

Input

• Dòng đầu tiên chứa \(2\) số nguyên \(n\) và \(m\) (\(1 \leq n \leq 100, 1 \leq m \leq 10\)).
• Dòng thứ \(i\) trong \(m\) dòng sau chứa số nguyên \(q_i\) – số phần tử của tập \(Q_i\) và \(q_i\) số nguyên xác định tập \(Q_i\).

Output

• Gồm một dòng chứa số nguyên là số lượng tìm được.

Example

5 2
3 1 2 3
2 2 4

34

Nguồn

Thầy Đông '21