시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 483 101 66 23.077%

문제

상근 선생님은 학생들에게 번호를 붙여주려고 한다. 상근이는 미술 선생님이기 때문에, 이름의 순서도 아름다워야 한다고 생각한다. 따라서, 다음과 같은 규칙을 지켜서 번호를 정하려고 한다.

같은 알파벳 순서로 시작하는 두 이름의 사이에는 모두 그 순서로 시작하는 단어가 있어야 한다.

예를 들어, 두 이름이 MARTHA와 MARY는 모두 MAR로 시작한다. 따라서, 그 두 단어 사이에는 MARCO나 MARVIN과 같이 MAR로 시작하는 이름만이 존재할 수 있다. (MAY는 그 사이에 있을 수 없다)

상근이의 규칙을 지키면서 학생들 이름의 순서를 정하는 방법의 수를 구하는 프로그램을 작성하시오. 참고로 사전순으로 정렬하면, 항상 상근이의 규칙을 지킬 수 있다. 

입력

첫째 줄에 이름의 수 N이 주어진다. (3 ≤ N ≤ 3000)

다음 N개 줄에는 이름이 한 줄에 하나씩 주어진다. 이름의 길이는 3000보다 작으며, 알파벳 대문자로만 이루어져 있다. 모든 이름은 중복되지 않는다.

출력

상근이의 규칙을 지키면서 순서를 정하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3
IVO
JASNA
JOSIPA

예제 출력 1

4

예제 입력 2

5
MARICA
MARTA
MATO
MARA
MARTINA

예제 출력 2

24

예제 입력 3

4
A
AA
AAA
AAAA

예제 출력 3

8
W3sicHJvYmxlbV9pZCI6IjMwODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVjNzc0XHViOTg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmMgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1YzVkMFx1YWM4YyBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZDk5XHVjNWVjXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmJmOFx1YzIyMCBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3NzRcdWI5ODRcdWM3NTggXHVjMjFjXHVjMTFjXHViM2M0IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZjY1x1YzU3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1Y2YxY1x1YzExYyBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjODE1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzE5XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWM3NzRcdWI5ODRcdWM3NTggXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFkZjggXHVjMjFjXHVjMTFjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViNDUwIFx1Yzc3NFx1Yjk4NFx1Yzc3NCBNQVJUSEFcdWM2NDAgTUFSWVx1YjI5NCBcdWJhYThcdWI0NTAgTUFSXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjggXHViNDUwIFx1YjJlOFx1YzViNCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgTUFSQ09cdWIwOTggTUFSVklOXHVhY2ZjIFx1YWMxOVx1Yzc3NCBNQVJcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1Yzc3NFx1Yjk4NFx1YjljY1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKE1BWVx1YjI5NCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWQ1NTlcdWMwZGRcdWI0ZTQgXHVjNzc0XHViOTg0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM4MTVcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjYzM4XHVhY2UwXHViODVjIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1NThcdWJhNzQsIFx1ZDU2ZFx1YzBjMSBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3NzRcdWI5ODRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAzMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzc0XHViOTg0XHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViOTg0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAzMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YzczY1x1YmE3MCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjNzc0XHViOTg0XHVjNzQwIFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVjMjFjXHVjMTFjXHViOTdjIFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzA4MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhFUktBQkUiLCJkZXNjcmlwdGlvbiI6IjxwPlRlYWNoZXIgSGVya2FiZSBoYXMgZGVjaWRlZCB0byByYW5rIGhpcyBzdHVkZW50cyBhZ2Fpbi4gVGhpcyB0aW1lLCBoZSB3YW50cyBoaXMgbGlzdCB0byBhbHNvIGJlIGFlc3RoZXRpY2FsbHkgcGxlYXNhbnQsIHNvIGhlIGhhcyBkZWNpZGVkIHRoYXQgc2ltaWxhciBuYW1lcyAodGhvc2UgYmVnaW5uaW5nIHdpdGggdGhlIHNhbWUgbGV0dGVyIG9yIHNlcXVlbmNlIG9mIGxldHRlcnMpIG11c3QgYmUgY2xvc2UgdG8gb25lIGFub3RoZXIgb24gdGhlIGxpc3QuIFRoZXJlZm9yZSwgaGUgaGFzIGRldmlzZWQgdGhlIGZvbGxvd2luZyBydWxlOjxcL3A+XHJcblxyXG48cD5Gb3IgZXZlcnkgdHdvIG5hbWVzIG9uIHRoZSBsaXN0IHRoYXQgYmVnaW4gd2l0aCB0aGUgc2FtZSBsZXR0ZXIgc2VxdWVuY2UsIGFsbCBuYW1lcyBiZXR3ZWVuIHRoZW0gb24gdGhlIGxpc3QgbXVzdCBhbHNvIGJlZ2luIHdpdGggdGhhdCBsZXR0ZXIgc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBjb25zaWRlciB0aGUgbmFtZXMgTUFSVEhBIGFuZCBNQVJZIChjaGFyYWN0ZXJzIGZyb20gYSBiZWF1dGlmdWwgc3RvcnkpLiBUaGV5IGJvdGggYmVnaW4gd2l0aCB0aGUgc2VxdWVuY2UgTUFSLCBzbyBuYW1lcyBiZWdpbm5pbmcgd2l0aCB0aGUgc2FtZSBzZXF1ZW5jZSAobGlrZSBNQVJDTyBhbmQgTUFSVklOKSBjYW4gYXBwZWFyIGluIGJldHdlZW4gKGJ1dCBub3QgTUFZLCBmb3IgZXhhbXBsZSkuPFwvcD5cclxuXHJcbjxwPk5vdGljZSB0aGF0IHRoZSBsZXhpY29ncmFwaGljYWxseSBzb3J0ZWQgb3JkZXJpbmcgYWx3YXlzIHNhdGlzZmllcyB0aGlzIHJ1bGUsIGJ1dCBpdCBpcyBieSBubyBtZWFucyB0aGUgb25seSB2YWxpZCBvcmRlcmluZy4gWW91ciB0YXNrIGlzIGRldGVybWluaW5nIGhvdyBtYW55IGRpZmZlcmVudCBvcmRlcmluZ3Mgc2F0aXNmeSB0aGUgcnVsZSwgaS5lLiBob3cgbWFueSBvcHRpb25zIHRlYWNoZXIgSGVya2FiZSBoYXMgZm9yIGhpcyByYW5raW5nIGxpc3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgzICZsZTsgTiAmbGU7IDMwMDApLCB0aGUgbnVtYmVyIG9mIG5hbWVzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhIHNpbmdsZSBuYW1lOiBhIHNlcXVlbmNlIG9mIGJldHdlZW4gMSBhbmQgMzAwMCAoaW5jbHVzaXZlKSB1cHBlcmNhc2UgRW5nbGlzaCBsZXR0ZXJzLiBUaGUgbmFtZXMgYXJlIGRpc3RpbmN0IGFuZCBnaXZlbiBpbiBubyBwYXJ0aWN1bGFyIG9yZGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG51bWJlciBvZiBwb3NzaWJsZSByYW5raW5nIGxpc3RzLCBtb2R1bG8gMSAwMDAgMDAwIDAwNy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #3 5번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: cokcjswo