시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 93 27 18 31.034%

문제

어젯밤에 나는 어렸을 때 가지고 놀던 장난감 상자 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로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

7

예제 입력 2

3 3
1 1
1 2
1 3

예제 출력 2

1

예제 입력 3

4 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 5

예제 출력 3

6
W3sicHJvYmxlbV9pZCI6IjI4MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwYjRcdWFjMDAgXHVjNWI0XHViODM4XHVjNzQ0IFx1YjU0YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHViMTgwXHViMzU4IFx1YzdhNVx1YjA5Y1x1YWMxMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWI0XHVjODJmXHViYzI0XHVjNWQwIFx1YjA5OFx1YjI5NCBcdWM1YjRcdWI4MzhcdWM3NDQgXHViNTRjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWIxODBcdWIzNTggXHVjN2E1XHViMDljXHVhYzEwIFx1YzBjMVx1Yzc5MCBOXHVhYzFjXHViOTdjIFx1Y2MzZFx1YWNlMFx1YzVkMFx1YzExYyBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YzBjMVx1Yzc5MFx1Yjk3YyBcdWM4ODAgXHViNGE0XHVjODAxXHVjNWVjXHViY2Y0XHViMmM4IFx1YjA5OFx1YjI5NCBNXHVjODg1XHViOTU4XHVjNzU4IFx1YzdhNVx1YjA5Y1x1YWMxMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM2MjRcdWI3YWJcdWIzZDlcdWM1NDggXHVhZTMwXHVjNWI1IFx1YzE4ZFx1YzVkMFx1YzExYyBcdWM3OGFcdWQ2MDBcdWM4NGNcdWIzNTggXHVjN2E1XHViMDljXHVhYzEwXHVjNzQ0IFx1YmNmNFx1YjJjOCwgXHViMGI0XHVhYzAwIFx1YzViNFx1YjgzOFx1Yzc0NCBcdWI1NGMsIFx1YmQ5OVx1YzVlYyBcdWM4ZmNcdWM1YzhcdWIzNTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YzBkZFx1YWMwMVx1YjA5Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFkZjggXHVjNzc0XHViOTg0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWFlMzBcdWM1YjVcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM3YTVcdWIwOWNcdWFjMTAgXHViOWM4XHViMmU0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWJkOTlcdWM1ZWNcdWM4ZmNcdWM1YjRcdWM1N2MgXHVhY2EwXHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjODg1XHViOTU4IFx1YzdhNVx1YjA5Y1x1YWMxMFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWJkOTlcdWM3NzRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWMwYzFcdWM3OTBcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHViYTc0XHVjMTFjIDFcdWJjODhcdWJkODBcdWQxMzAgTVx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZDk5XHVjNWVjXHVjOGZjXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI4MzhcdWM3NDRcdWM4MDFcdWJkODBcdWQxMzAgXHVjODE1XHViOWFjXHVjODE1XHViM2M4XHVjNzU4IFx1YWRjMFx1YzdhY1x1YzYwMFx1YjM1OCBcdWIwOThcdWIyOTQgXHVkNTZkXHVjMGMxIFx1ZDU1YyBcdWJjMTVcdWMyYTRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWM3YTVcdWIwOWNcdWFjMTBcdWM3NDQgXHViMTIzXHVjNWM4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzc3NCBcdWMwYzFcdWM3OTBcdWIyOTQgXHViMGI0XHVhYzAwIFx1YzgxNVx1YjlhY1x1ZDU1YyBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmNjXHVhYzAwXHViY2Y0XHViMmU0LiBcdWM3YTVcdWIwOWNcdWFjMTBcdWI0ZTRcdWM3NzQgXHViNGE0XHVjOGZkXHViYzE1XHVjOGZkIFx1YjRlNFx1YzViNFx1YWMwMFx1Yzc4OFx1YjJlNC4gXHVjMmVjXHVjOWMwXHVjNWI0XHViMjk0IFx1YWMxOVx1Yzc0MCBcdWM4ODVcdWI5NThcdWM3NTggXHVjN2E1XHViMDljXHVhYzEwXHVjNzc4XHViMzcwXHViM2M0IFx1YzVlY1x1YjdlYyBcdWMwYzFcdWM3OTBcdWM1ZDAgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4XHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM1YjRcdWI4MzhcdWM3NDQgXHVjODAxIFx1Y2Q5NFx1YzViNVx1YzVkMCBcdWM4MTZcdWM1YjRcdWM3ODhcdWIyZTRcdWJjZjRcdWIyYzggXHVjOWMwXHVhZTA4IFx1YjBiNFx1YWMwMCBcdWM1YmNcdWJhMzhcdWIwOTggXHVjMjFjXHVjMjE4XHVkNTY4XHVjNzQ0IFx1Yzc4M1x1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3YTVcdWIwOWNcdWFjMTBcdWM3NDQgXHVkNTZkXHVjMGMxIFx1YjBiNCBcdWFjYzFcdWM1ZDAgXHViNDUwXHVjNWI0IFx1YzgwOFx1YjMwMCBcdWM1YjRcdWI4MzhcdWM3NDQgXHVjODAxXHVjNzU4IFx1YzIxY1x1YzIxOFx1ZDU2OFx1Yzc0NCBcdWM3ODNcdWM5YzAgXHVjNTRhXHVjNTQ0XHVjNTdjXHVhY2EwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIwYjQgXHViYzI5XHVjNzQwIFx1Yzg4MVx1YjJlNC4gXHViYzE1XHVjMmE0XHViOTdjIFx1YjE5M1x1YWUzMFx1YzVkMFx1YjI5NCBcdWIxMDhcdWJiMzRcdWIwOThcdWIzYzQgXHVjODgxXHViMmU0LiBcdWM3N2NcdWJkODAgXHViYzE1XHVjMmE0XHViOWNjIFx1YzEyMFx1ZDBkZFx1ZDU3NFx1YzExYyBcdWIwYjQgXHVhY2MxXHVjNWQwIFx1YjQ1MFx1YzViNFx1YzU3YyBcdWFjYTBcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViYWE4XHViNGUwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWM3YTVcdWIwOWNcdWFjMTBcdWM3NzQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1YjA5OFx1YjI5NCBcdWMyMWNcdWMyMThcdWQ1NjhcdWM3NDQgXHVjNzgzXHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWFjODMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjODg1XHViOTU4XHVjNzU4IFx1YzdhNVx1YjA5Y1x1YWMxMFx1Yzc3NCBcdWMxMjBcdWQwZGRcdWQ1NWMgXHViYzE1XHVjMmE0IFx1YzU0OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWFjOGMgXHViYzE1XHVjMmE0XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjZDFkIFx1YmE4NyBcdWFjMDBcdWM5YzBcdWIwOTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxLDAwMCwwMDAsIDEgJmxlOyBNICZsZTsgMjApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViYzE1XHVjMmE0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM3YTVcdWIwOWNcdWFjMTBcdWM3NTggXHVjODg1XHViOTU4XHVjNzU4IFx1YzIxOCBLPHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWM1YjRcdWI1YTQgXHVjODg1XHViOTU4XHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjE4XHViMjk0IEs8c3ViPmk8XC9zdWI+XHVjNzc0XHVhY2UwLCBcdWIyZTRcdWM3NGMgXHVjMjJiXHVjNzkwIEs8c3ViPmk8XC9zdWI+XHVhYzFjXHViMjk0IFx1YzdhNVx1YjA5Y1x1YWMxMCBcdWM4ODVcdWI5NThcdWM3NzRcdWIyZTQuJm5ic3A7KDAgJmxlOyBLPHN1Yj5pPFwvc3ViPiAmbGU7IE0pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYThcdWI0ZTAgXHVjODg1XHViOTU4XHVjNzU4IFx1YzdhNVx1YjA5Y1x1YWMxMFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWFjOGMgXHViYzE1XHVjMmE0XHViOTdjIFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgwMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktPXHUwMTYwQVJFIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBmb3VuZCBOIGJveGVzIHdpdGggdmFyaW91cyBmb3Jnb3R0ZW4gdG95cyBhdCBoaXMgYXR0aWMuIFRoZXJlIGFyZSBNIGRpZmZlcmVudCB0b3lzLCBudW1iZXJlZCAxIHRocm91Z2ggTSwgYnV0IGVhY2ggb2YgdGhvc2UgY2FuIGFwcGVhciBtdWx0aXBsZSB0aW1lcyBhY3Jvc3MgdmFyaW91cyBib3hlcy48XC9wPlxyXG5cclxuPHA+TWlya28gZGVjaWRlZCB0aGF0IGhlIHdpbGwgY2hvb3NlIHNvbWUgYm94ZXMgaW4gYSB3YXkgdGhhdCB0aGVyZSBpcyBhdCBsZWFzdCBvbmUgdG95IG9mIGVhY2gga2luZCBwcmVzZW50LCBhbmQgdGhyb3cgdGhlIHJlc3Qgb2YgdGhlIGJveGVzIGF3YXkuPFwvcD5cclxuXHJcbjxwPkRldGVybWluZSB0aGUgbnVtYmVyIG9mIHdheXMgaW4gd2hpY2ggTWlya28gY2FuIGRvIHRoaXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE4gJmxlOyAxIDAwMCAwMDAsIDEgJmxlOyBNICZsZTsgMjApLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhbiBpbnRlZ2VyIEs8c3ViPmk8XC9zdWI+ICgwICZsZTsgSzxzdWI+aTxcL3N1Yj4gJmxlOyBNKSBmb2xsb3dlZCBieSBLPHN1Yj5pPFwvc3ViPiBkaXN0aW5jdCBpbnRlZ2VycyBmcm9tIGludGVydmFsIFsxLCBNXSwgcmVwcmVzZW50aW5nIHRoZSB0b3lzIGluIHRoYXQgYm94LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgcmVxdWVzdGVkIG51bWJlciBvZiB3YXlzIG1vZHVsbyAxIDAwMCAwMDAgMDA3LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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