시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 89 23 16 28.571%

문제

어젯밤에 나는 어렸을 때 가지고 놀던 장난감 상자 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+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjODg1XHViOTU4XHVjNzU4IFx1YzdhNVx1YjA5Y1x1YWMxMFx1Yzc3NCBcdWMxMjBcdWQwZGRcdWQ1NWMgXHViYzE1XHVjMmE0IFx1YzU0OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWFjOGMgXHViYzE1XHVjMmE0XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjZDFkIFx1YmE4N1x1YWMwMFx1YzljMFx1YjA5OCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwLDAwMCwgMSAmbGU7IE0gJmxlOyAyMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzdhNVx1YjA5Y1x1YWMxMFx1Yzc1OCBcdWM4ODVcdWI5NThcdWM3NTggXHVjMjE4IEs8c3ViPmk8XC9zdWI+XHVjNjQwIFx1YzViNFx1YjVhNCBcdWM4ODVcdWI5NThcdWFjMDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0XHVjOWMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgSzxzdWI+aTxcL3N1Yj5cdWM3NzRcdWFjZTAsIFx1YjJlNFx1Yzc0YyBcdWMyMmJcdWM3OTAgSzxzdWI+aTxcL3N1Yj5cdWFjMWNcdWIyOTQgXHVjN2E1XHViMDljXHVhYzEwIFx1Yzg4NVx1Yjk1OFx1Yzc3NFx1YjJlNC4mbmJzcDsoMCAmbGU7IEs8c3ViPmk8XC9zdWI+ICZsZTsgTSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWM4ODVcdWI5NThcdWM3NTggXHVjN2E1XHViMDljXHVhYzEwXHVjNzc0IFx1YjRlNFx1YzViNFx1Yzc4OFx1YWM4YyBcdWJjMTVcdWMyYTRcdWI5N2MgXHVhY2UwXHViOTc0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS09cdTAxNjBBUkUiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGZvdW5kIE4gYm94ZXMgd2l0aCB2YXJpb3VzIGZvcmdvdHRlbiB0b3lzIGF0IGhpcyBhdHRpYy4gVGhlcmUgYXJlIE0gZGlmZmVyZW50IHRveXMsIG51bWJlcmVkIDEgdGhyb3VnaCBNLCBidXQgZWFjaCBvZiB0aG9zZSBjYW4gYXBwZWFyIG11bHRpcGxlIHRpbWVzIGFjcm9zcyB2YXJpb3VzIGJveGVzLjxcL3A+XHJcblxyXG48cD5NaXJrbyBkZWNpZGVkIHRoYXQgaGUgd2lsbCBjaG9vc2Ugc29tZSBib3hlcyBpbiBhIHdheSB0aGF0IHRoZXJlIGlzIGF0IGxlYXN0IG9uZSB0b3kgb2YgZWFjaCBraW5kIHByZXNlbnQsIGFuZCB0aHJvdyB0aGUgcmVzdCBvZiB0aGUgYm94ZXMgYXdheS48XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBudW1iZXIgb2Ygd2F5cyBpbiB3aGljaCBNaXJrbyBjYW4gZG8gdGhpcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNICgxICZsZTsgTiAmbGU7IDEgMDAwIDAwMCwgMSAmbGU7IE0gJmxlOyAyMCkuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGFuIGludGVnZXIgSzxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBLPHN1Yj5pPFwvc3ViPiAmbGU7IE0pIGZvbGxvd2VkIGJ5IEs8c3ViPmk8XC9zdWI+IGRpc3RpbmN0IGludGVnZXJzIGZyb20gaW50ZXJ2YWwgWzEsIE1dLCByZXByZXNlbnRpbmcgdGhlIHRveXMgaW4gdGhhdCBib3guPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSByZXF1ZXN0ZWQgbnVtYmVyIG9mIHdheXMgbW9kdWxvIDEgMDAwIDAwMCAwMDcuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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