동아리 회장 태윤이는 \(M\) 가지 업무를 모두 처리해 줄 부원 조합을 찾고 있다. 부원은 \(N\) 명이며, 각 부원은 자신이 처리할 수 있는 업무들의 목록을 가진다.

부원들의 부분집합(공집합 제외)을 골랐을 때, 그 부원들이 처리할 수 있는 업무를 합쳐 \(M\) 가지 업무를 모두 커버할 수 있으면 그 조합을 "완전한 조합"이라 부른다.

완전한 조합의 개수를 구하여라.

• \(1 \le N \le 20\)
• \(1 \le M \le 20\)
• \(0 \le k \le M\), 한 줄 안의 업무 번호는 서로 다르다.

첫째 줄에 부원 수 \(N\) 과 업무 수 \(M\) 이 주어진다.

이어지는 \(N\) 개의 줄에 각각 한 부원의 정보가 주어진다. 각 줄은 그 부원이 처리할 수 있는 업무 수 \(k\) 와 이어서 \(k\) 개의 업무 번호 (\(1\) 이상 \(M\) 이하)로 이루어진다. \(k=0\) 이면 줄에는 \(0\) 만 주어진다.

완전한 조합의 개수를 한 줄에 출력한다.

riseoj 작성

출처 Original