The cows want to form an expeditionary team to explore the wooded area at the edge of Farmer John's territory. Exploring turns out to be an activity that requires more skill than just standing in the pasture and grazing.
The team of $C$ ($1 \le C \le 20$) cows numbered 1..$C$ must include cows that are able to navigate through the woods without getting lost, fend off big nasty creatures, tell jokes to keep the morale high, etc. At least one cow on the team must possess each of these $A$ ($1 \le A \le 20$) special abilities numbered 1..$A$. Some cows have only one ability, but many have multiple abilities; some cows are just freeloaders who are completely useless.
Given a list of all the cows and the abilities of each cow, compute the number of different exploration teams that the cows can form, such that the team as a whole has all the given abilities.
Input
- Line 1: Two integers, $C$ and $A$
- Lines 2..$A$+1: Each line contains a set of space-separated integers describing an ability. Line 2 describes ability 1; line 3 describes ability 2; etc. The first integer on each line, $K$ ($1 \le K \le C$), is the number of cows with this ability. The following $K$ integers represent the cows who have the ability.
Output
- Line 1: An integer representing the number of different exploration teams that the cows can form.
Examples
Input 1
4 2 2 3 1 1 2
Output 1
6
Input Details
There are 4 cows and 2 abilities. Cows 1 and 3 have ability 1, while only cow 2 has ability 2. Cow 4 is relatively talentless.
Output Details
The possible exploration teams are: {1, 2}, {2, 3}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, and {1, 2, 3, 4}.
Problem credits: Percy Liang, 2004