어릴 적 장난감 상자
시간 제한2초메모리 제한128 MB
각 상자를 최대 20비트 마스크로 표현할 때, 모든 장난감 종류를 합집합으로 포함하는 상자 부분집합의 개수를 1,000,000,007로 나눈 나머지로 구합니다.
문제
창고에서 N개의 장난감 상자를 발견했다. 상자들을 살펴보니 총 M종류의 장난감이 들어 있었다. 각 장난감 종류에는 1번부터 M번까지 번호를 붙였다.
상자 하나에는 여러 종류의 장난감이 섞여 있을 수 있고, 같은 종류의 장난감이 여러 상자에 나뉘어 들어 있을 수도 있다.
방이 좁아서 모든 상자를 둘 수는 없다. 대신 일부 상자를 골라 곁에 두려고 한다. 고른 상자들 안에는 1번부터 M번까지 모든 종류의 장난감이 적어도 하나씩 들어 있어야 한다.
이 조건을 만족하도록 상자를 고르는 방법의 수를 구하시오. 상자는 서로 다른 상자로 구분한다.
입력
첫째 줄에 상자의 개수 N과 장난감 종류 수 M이 주어진다. (1 <= N <= 1,000,000, 1 <= M <= 20)
다음 N개 줄의 i번째 줄에는 i번째 상자에 들어 있는 장난감 종류 정보가 주어진다. 첫 수는 K_i이고, 이어서 그 상자에 들어 있는 장난감 종류 번호 K_i개가 주어진다. (0 <= K_i <= M)
장난감 종류 번호는 1 이상 M 이하이다.
출력
모든 종류의 장난감이 적어도 하나씩 포함되도록 상자를 고르는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.