도시에는 \(N\) 개의 구역이 \(1\) 번부터 \(N\) 번까지 있고, 설치 가능한 안테나가 \(M\) 개 있습니다. \(i\) 번 안테나는 어떤 구역들의 집합을 신호로 덮습니다.

\(M\) 개의 안테나 중 일부를 골라(아무것도 안 고를 수도 있음) 그들이 덮는 구역의 합집합이 정확히 전체 \(N\) 개 구역 전부가 되도록 하는 방법의 수를 구하세요. 안테나의 부분집합 자체가 다르면 다른 방법으로 셉니다.

답이 매우 클 수 있으므로 \(1\,000\,000\,007\) 로 나눈 나머지를 출력합니다. \(N \le 16\) 이므로 덮인 구역 집합을 비트마스크 상태로 두는 DP로 셀 수 있습니다.

• \(1 \le N \le 16\)
• \(1 \le M \le 30\)
• 각 안테나가 덮는 구역 번호는 서로 다르고 \(1\) 이상 \(N\) 이하입니다.

첫 줄에 구역 수 \(N\) 과 안테나 수 \(M\) 이 주어집니다.

이어서 \(M\) 개의 줄에 각 안테나가 주어집니다. 각 줄은 그 안테나가 덮는 구역의 개수 \(k\) 와 \(k\) 개의 구역 번호로 이루어집니다.

전체 구역을 정확히 덮는 안테나 부분집합의 수를 \(1\,000\,000\,007\) 로 나눈 나머지를 출력합니다.

riseoj 작성

출처 Original