시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 454 | 202 | 149 | 46.708% |
어젯밤에 나는 어렸을 때 가지고 놀던 장난감 상자 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
3 3 1 1 1 2 1 3
1
4 5 2 2 3 2 1 2 4 1 2 3 5 4 1 2 4 5
6