eolymp
bolt
Try our new interface for solving problems
Problems

Avoiding Partitions

Avoiding Partitions

Time limit 1 second
Memory limit 64 MiB

A partition of a set S = {1, 2, ..., n} is a collection P of sets P = {P_1, P_2, ..., P_k} such that UP_i = S and P_iP_j = for ij. An example of a partition for n = 5 is P_1 = {1, 3}, P_2 = {2, 4, 5}.

The partition is said to avoid set Q if none of P_i has Q as a subset. For example, the partition above avoids sets {1, 2} and {3, 4} but doesn't avoid {1, 3} nor {2}.

Given n and a collection of sets Q_1, Q_2, ..., Q_l find the number of partitions of S that avoid each of Q_i.

Input data

The first line of the input file contains two integer numbers n and l (1n100, 0l10). The following l lines describe sets to avoid. Each line starts with one integer number q_i - the size of the set, followed by q_i numbers - the elements of the set.

Output data

Output one integer number the number of partitions avoiding each of Q_i.

Examples

Input example #1
5 2
3  1 2 3
2  2 4
Output example #1
34
Author Andrew Stankevich
Source Andrew Stankevich Contest 32, Petrozavodsk Summer Training Camp, Wednesday, September 3, 2008