시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 35 8 5 45.455%

문제

어젯밤에 나는 어렸을 때 가지고 놀던 장난감 상자 N개를 창고에서 발견했다. 상자를 좀 뒤적여보니 나는 M종류의 장난감을 가지고 있었다. 오랫동안 기억 속에서 잊혀졌던 장난감을 보니, 내가 어렸을 때, 붙여 주었던 이름이 생각난다. 하지만, 그 이름이 모두 기억나지 않는다. 장난감 마다 숫자를 붙여주어야 겠다. 같은 종류 장난감은 모두 같은 번호를 붙이기로 했다. 상자를 살펴보면서 1번부터 M번까지 번호를 붙여주었다.

어렸을적부터 정리정돈의 귀재였던 나는 항상 한 박스에는 한 종류의 장난감을 넣었다. 하지만, 이 상자는 내가 정리한 것이 아닌가보다. 장난감들이 뒤죽박죽 들어가있다. 심지어는 같은 종류의 장난감인데도 여러 상자에 나누어져있는 경우도 있다.

이렇게 어렸을 적 추억에 젖어있다보니 지금 내가 얼머나 순수함을 잃었는지를 생각하게 된다. 장난감을 항상 내 곁에 두어 절대 어렸을 적의 순수함을 잃지 않아야겠다.

내 방은 좁다. 박스를 놓기에는 너무나도 좁다. 일부 박스만 선택해서 내 곁에 두어야 겠다. 하지만, 모든 종류의 장난감이 있어야 나는 순수함을 잃지 않을 것 같다.

모든 종류의 장난감이 선택한 박스 안에 들어있게 박스를 선택하는 방법은 총 몇가지나 있을까?

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 20)

다음 N개 줄에는 각 박스에 들어있는 장난감의 종류의 수 Ki와 어떤 종류가 들어있는지 주어진다. 첫 번째 수는 Ki이고, 다음 숫자 Ki개는 장난감 종류이다. (0 ≤ Ki ≤ M)

출력

첫째 줄에 모든 종류의 장난감이 들어있게 박스를 고르는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

3 3
3 1 2 3
3 1 2 3
3 1 2 3

예제 출력

7

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #6 6번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: sosfd