시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 20 7 3 33.333%

문제

어떤 문자열 S의 길이가 k인 부분문자열의 집합을 T(S, k)라 표현하자. 예를 들어 S="ABABA", k=2일 때, T(S, k)={"AB", "BA"}가 된다. {"AB", "BA", "AB", "BA"}가 아닌 이유는 집합은 같은 원소(중복된 원소)를 허용하지 않기 때문이다.

N 종류의 문자로 이루어진 길이가 k인 문자열들의 집합 X가 주어졌을 때, T(S, k)가 X의 부분집합이 되도록 하는 S의 개수를 구하는 프로그램을 작성하시오. 단 S의 길이는 L이어야 한다.

예를 들어 X={"ABB", "BCA", "BCD", "CAB", "CDD", "DDA"}인 경우에는 "BCABB", "BCDDA"의 두 가지 경우가 있다.

입력

첫째 줄에 N(1≤N≤26), L(1≤L≤100), M(1≤M≤600)이 주어진다. M은 집합 X의 크기이다. 다음 줄에는 X를 이루는 문자열들이 주어진다. 각 문자열들의 길이는 같으며, 10 이하이다. 입력으로는 대문자만 주어진다.

출력

첫째 줄에 S의 개수를 출력한다. 이 값은 32-bit signed integer(VC에서 int)의 범위를 넘지 않는다.

예제 입력 1

5 4 5
E D C B A

예제 출력 1

625
W3sicHJvYmxlbV9pZCI6IjIzMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHViY2Y1XHVjNmQwXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIGtcdWM3NzggXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0NCBUKFMsIGspXHViNzdjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1Yzc5MC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBTPSZxdW90O0FCQUJBJnF1b3Q7LCBrPTJcdWM3N2MgXHViNTRjLCBUKFMsIGspPXsmcXVvdDtBQiZxdW90OywgJnF1b3Q7QkEmcXVvdDt9XHVhYzAwIFx1YjQxY1x1YjJlNC4geyZxdW90O0FCJnF1b3Q7LCAmcXVvdDtCQSZxdW90OywgJnF1b3Q7QUImcXVvdDssICZxdW90O0JBJnF1b3Q7fVx1YWMwMCBcdWM1NDRcdWIyY2MgXHVjNzc0XHVjNzIwXHViMjk0IFx1YzlkMVx1ZDU2OVx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVjNmQwXHVjMThjKFx1YzkxMVx1YmNmNVx1YjQxYyBcdWM2ZDBcdWMxOGMpXHViOTdjIFx1ZDVjOFx1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbjxwPk4gXHVjODg1XHViOTU4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0XHVhYzAwIGtcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHViNGU0XHVjNzU4IFx1YzlkMVx1ZDU2OSBYXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFQoUywgaylcdWFjMDAgWFx1Yzc1OCBcdWJkODBcdWJkODRcdWM5ZDFcdWQ1NjlcdWM3NzQgXHViNDE4XHViM2M0XHViODVkIFx1ZDU1OFx1YjI5NCBTXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViMmU4IFNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IExcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgWD17JnF1b3Q7QUJCJnF1b3Q7LCAmcXVvdDtCQ0EmcXVvdDssICZxdW90O0JDRCZxdW90OywgJnF1b3Q7Q0FCJnF1b3Q7LCAmcXVvdDtDREQmcXVvdDssICZxdW90O0REQSZxdW90O31cdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O0JDQUJCJnF1b3Q7LCAmcXVvdDtCQ0REQSZxdW90O1x1Yzc1OCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxJmxlO04mbGU7MjYpLCBMKDEmbGU7TCZsZTsxMDApLCBNKDEmbGU7TSZsZTs2MDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTVx1Yzc0MCBcdWM5ZDFcdWQ1NjkgWFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgWFx1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YjRlNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzNjXHViYTcwLCAxMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1Y1x1YjI5NCBcdWIzMDBcdWJiMzhcdWM3OTBcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBTXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMzItYml0IHNpZ25lZCBpbnRlZ2VyKFZDXHVjNWQwXHVjMTFjIGludClcdWM3NTggXHViYzk0XHVjNzA0XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMzE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGVjb3JhdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBTdWx0YW4gb2YgU3lsdmFuaWEgbG92ZXMgdGhyb3dpbmcgcGFydGllcywgYmVjYXVzZSB0aGF0IGdpdmVzIGhpbSBhIHJlYXNvbiB0byBkZWNvcmF0ZSB0aGUgcGFsYWNlLiBIZSBwYXJ0aWN1bGFybHkgbGlrZXMgZGVjb3JhdGlvbnMgY2FsbGVkIHN0cmVhbWVycyBtYWRlIHVwIG9mIGRpZmZlcmVudCBiZWFkcyBzdHJ1bmcgdG9nZXRoZXIgb24gYSBzdHJpbmcgYW5kIGh1bmcgZnJvbSB0aGUgY2VpbGluZy4gTm93LCBsaWtlIG1vc3QgU3VsdGFucywgaGUgaXMgdmVyeSBwYXJ0aWN1bGFyIGFib3V0IGV2ZXJ5dGhpbmcsIGluY2x1ZGluZyB0aGVzZSBzdHJ1bmcgZGVjb3JhdGlvbnMuIFNwZWNpJm1hY3I7Y2FsbHksIGhlIG9ubHkgbGlrZXMgY2VydGFpbiBjb21iaW5hdGlvbnMgb2YgYmVhZHMgdG8gYmUgdXNlZCBvbiB0aGUgc3RyZWFtZXJzLiBGb3IgZXhhbXBsZSwgaWYgdGhlcmUgYXJlIGZvdXIgZGkmcmVnO2VyZW50IHR5cGVzIG9mIGJlYWRzIC0gQSwgQiwgQyBhbmQgRCAtIHRoZSBTdWx0YW4gbWlnaHQgc2F5ICZxdW90O0l0IHBsZWFzZXMgaGlzIGhpZ2huZXNzIHRoYXQgb25seSB0aGUgY29tYmluYXRpb25zIEFCQiwgQkNBLCBCQ0QsIENBQiwgQ0REIGFuZCBEREEgYXBwZWFyIGluIHRoZSBzdHJlYW1lcnMgYXQgdG9uaWdodCYjMzk7cyBwYXJ0eSZxdW90Oy4gVGhpcywgbmVlZGxlc3MgdG8gc2F5LCBwdXRzIGEgc2V2ZXJlIGxpbWl0IG9uIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHN0cmVhbWVycyBwb3NzaWJsZS4gRm9yIGV4YW1wbGUsIGlmIHRoZSBsZW5ndGggb2YgdGhlIHN0cmVhbWVycyB3YXMgNSwgdGhlbiB0aGUgb25seSBwb3NzaWJsZSBzdHJlYW1zIG9mIGJlYWRzIHdvdWxkIGJlIEJDQUJCIGFuZCBCQ0REQSAoc3RyaW5ncyBzdWNoIGFzIEFCQkNBIGNvdWxkIG5vdCBiZSB1c2VkIGJlY2F1c2UgQkJDIGlzIG5vdCBhbiBhcHByb3ZlZCBjb21iaW5hdGlvbikuIFNpbmNlIHRoZSBTdWx0YW4gbGlrZXMgdmFyaWV0eSwgaXQgaXMgaW1wb3J0YW50IHRvIGtub3cgdGhlIHRvdGFsIG51bWJlciBvZiBzdHJlYW1lcnMgcG9zc2libGUsIGdpdmVuIGEgbGVuZ3RoIGFuZCB0aGUgY3VycmVudCBiZWFkIGNvbWJpbmF0aW9ucyB3aGljaCB0aWNrbGUgdGhlIFN1bHRhbiYjMzk7cyBmYW5jeS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBFYWNoIGNhc2Ugd2lsbCBjb25zaXN0IG9mIHR3byBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHRocmVlIHBvc2l0aXZlIGludGVnZXJzIG4sIGwgYW5kIG0sIHdoZXJlIG4gaW5kaWNhdGVzIHRoZSBudW1iZXIgb2YgYmVhZCB0eXBlcywgbCBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBzdHJlYW1lcnMgYW5kIG0gaW5kaWNhdGVzIHRoZSBudW1iZXIgb2YgYmVhZCBjb21iaW5hdGlvbnMgd2hpY2ggdGhlIFN1bHRhbiBsaWtlcy4gVGhlIG1heGltdW0gdmFsdWVzIGZvciBuLCBsIGFuZCBtIHdpbGwgYmUgMjYsIDEwMCBhbmQgNjAwLCByZXNwZWN0aXZlbHkuIFRoZSBuZXh0IGxpbmUgd2lsbCBjb250YWluIHRoZSBtIGNvbWJpbmF0aW9ucy4gRWFjaCBjb21iaW5hdGlvbiB3aWxsIGJlIG9mIHRoZSBzYW1lIGxlbmd0aCAoYmV0d2VlbiAxIGFuZCAxMCkgYW5kIHdpbGwgYmUgc2VwYXJhdGVkIHVzaW5nIGEgc2luZ2xlIHNwYWNlLiBBbGwgY29tYmluYXRpb25zIHdpbGwgbWFrZSB1c2Ugb2Ygb25seSB0aGUgdXBwZXJjYXNlIGxldHRlcnMgb2YgdGhlIGFscGhhYmV0LiBBbiBpbnB1dCBsaW5lIG9mIDAgMCAwIHdpbGwgdGVybWluYXRlIGlucHV0IGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBsaW5lIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBzdHJlYW1lcnMuIEFsbCBhbnN3ZXJzIHdpbGwgYmUgd2l0aGluIHRoZSByYW5nZSBvZiBhIDMyLWJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==