소들은 Farmer John의 땅 가장자리 숲을 탐험할 원정대를 만들고 싶다. 탐험은 목초지에 서서 풀을 먹는 것보다 더 많은 기술이 필요하다.
1..$C$번 소 $C$마리($1 \le C \le 20$)로 구성하는 팀에는 숲에서 길을 잃지 않기, 크고 사나운 생물 물리치기, 농담으로 사기 높이기 등의 능력이 필요하다. 1..$A$번 특별 능력 $A$개($1 \le A \le 20$) 각각을 적어도 한 마리가 가져야 한다. 한 능력만 있는 소도 있고 많은 소는 여러 능력이 있으며, 전혀 쓸모없는 무임승차 소도 있다.
모든 소와 각 능력이 주어질 때, 팀 전체가 모든 주어진 능력을 가지는 서로 다른 탐험대 수를 구하여라.
입력
- 1번째 줄: 두 정수 $C$와 $A$.
- 2..$A$+1번째 줄: 각 줄은 공백으로 구분된 정수로 한 능력을 설명한다. 2번째 줄은 능력 1, 3번째 줄은 능력 2 등이다. 첫 정수 $K$($1 \le K \le C$)는 이 능력이 있는 소 수이고, 다음 $K$개 정수는 그 소들을 나타낸다.
출력
- 1번째 줄: 만들 수 있는 서로 다른 탐험대 수인 정수.
예제
입력 1
4 2 2 3 1 1 2
출력 1
6
참고
입력 설명
소 4마리와 능력 2개가 있다. 소 1과 3은 능력 1, 소 2만 능력 2를 갖는다. 소 4는 별로 재능이 없다.
출력 설명
가능한 탐험대는 $\{1, 2\}$, $\{2, 3\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{2, 3, 4\}$, $\{1, 2, 3, 4\}$이다.
문제 작성자: Percy Liang, 2004