시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 428 176 128 42.809%

문제

상근이는 자신이 만든 폰트를 테스트하기 위한 문장 만드려고 한다. 폰트에는 알파벳 소문자만 포함되어 있기 때문에, 문장은 알파벳 소문자로 작성해야 한다.

테스트 문장에는 알파벳 소문자 26개가 모두 포함되어 있어야 한다.

사실 문제를 많이 풀어본 사람이라면, 문제를 여기까지 읽어도 무슨 문제인지 감이 잡혀야 한다.

상근이는 단어 N개가 포함되어 있는 사전을 하나 가지고 있다. 테스트 문장은 사전에 포함된 단어만 이용해서 만들 수 있으며, 각 단어는 한 번씩만 사용해야 한다. 또, 단어의 순서는 중요하지 않다. (“uvijek jedem sarmu” 와 “jedem sarmu uvijek”는 같은 문장이다)

상근이가 만들 수 있는 테스트 문장의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다.

출력

상근이가 만들 수 있는 테스트 문장의 개수를 출력한다. 

예제 입력 1

9
the
quick
brown
fox
jumps
over
a
sleazy
dog

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6Ijk5OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZjBcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHViOWNjXHViNGUwIFx1ZDNmMFx1ZDJiOFx1Yjk3YyBcdWQxNGNcdWMyYTRcdWQyYjhcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YmIzOFx1YzdhNSBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQzZjBcdWQyYjhcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjljYyBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViYjM4XHVjN2E1XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzkxXHVjMTMxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1YmIzOFx1YzdhNVx1YzVkMFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwIDI2XHVhYzFjXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHVjMmU0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI5Y2VcdWM3NzQgXHVkNDgwXHVjNWI0XHViY2Y4IFx1YzBhY1x1Yjc4Y1x1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHViYjM4XHVjODFjXHViOTdjIFx1YzVlY1x1YWUzMFx1YWU0Y1x1YzljMCBcdWM3N2RcdWM1YjRcdWIzYzQgXHViYjM0XHVjMmE4IFx1YmIzOFx1YzgxY1x1Yzc3OFx1YzljMCBcdWFjMTBcdWM3NzQgXHVjN2ExXHVkNjAwXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlOFx1YzViNCBOXHVhYzFjXHVhYzAwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVjODA0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHViYjM4XHVjN2E1XHVjNzQwIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHViMmU4XHVjNWI0XHViOWNjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YjJlOFx1YzViNFx1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNTI5XHViOWNjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWM5MTFcdWM2OTRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0LiAoJmxkcXVvO3V2aWplayBqZWRlbSBzYXJtdSZyZHF1bzsgXHVjNjQwICZsZHF1bztqZWRlbSBzYXJtdSB1dmlqZWsmcmRxdW87XHViMjk0IFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3YTVcdWM3NzRcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHViYjM4XHVjN2E1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxICZsZTsgTiAmbGU7IDI1KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YzkxMVx1YmNmNVx1YjQxOFx1YjI5NCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YmIzOFx1YzdhNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk5OTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGT05UIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgSXZpY2EgZ290IGhpbXNlbGYgYSBzdW1tZXIgam9iIGF0IGEgY29tcGFueSB0aGF0IHByb2R1Y2VzIGNvbXB1dGVyIGZvbnRzLiBUaGUgYnJhbmNoIG9mIHRoZSBjb21wYW55IHdoZXJlIEl2aWNhIHdvcmtzIGF0IHNwZWNpYWxpc2VzIGluIHRlc3RpbmcgY29tcHV0ZXIgZm9udHMgYW5kIEl2aWNhJiMzOTtzIHRlYW0gaXMgcmVzcG9uc2libGUgb2YgdGVzdGluZyBvbmx5IGxvd2VyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbGV0dGVycyBhcmUgdGVzdGVkIHNvIHRoYXQgdmFyaW91cyBzZW50ZW5jZXMgdXNpbmcgdGhvc2UgbGV0dGVycyBhcmUgcHJpbnRlZCBvdXQgYW5kIHRoZW4gbWFudWFsbHkgKG1vcmUgYWNjdXJhdGVseSwgdmlzdWFsbHkpIGNoZWNrZWQgaWYgZXZlcnl0aGluZyBpcyBhcnJhbmdlZCBwcm9wZXJseS4gT25seSBzZW50ZW5jZXMgd2hpY2ggY29udGFpbiBhbGwgMjYgbG93ZXJjYXNlIGxldHRlciBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCAoYS16KSBhcmUgdXNlZCBmb3IgdGVzdGluZyBwdXJwb3Nlcy4gVGhlc2Ugc2VudGVuY2VzIGFyZSBjYWxsZWQgdGVzdCBzZW50ZW5jZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSYjMzk7dmUgcHJvYmFibHkgYWxyZWFkeSBhc3N1bWVkIHRoYXQgSXZpY2EmIzM5O3Mgam9iIGlzIHRvIGZpbmQgdGVzdCBzZW50ZW5jZXMuIEhlIGhhcyBhIGRpY3Rpb25hcnkgd2hpY2ggY29uc2lzdHMgb2YgTiB3b3JkcyBhbmQgaGFzIHRvIGNhbGN1bGF0ZSBob3cgbWFueSBkaWZmZXJlbnQgdGVzdCBzZW50ZW5jZXMgY2FuIGJlIG1hZGUgb3V0IG9mIHRob3NlIHdvcmRzLiBFdmVyeSB3b3JkIGZyb20gdGhlIGRpY3Rpb25hcnkgY2FuIGJlIHVzZWQgb25seSBvbmNlIGluIHRoZSBzZW50ZW5jZSBhbmQgdGhlIG9yZGVyIG9mIHRoZSB3b3JkcyBpbiB0aGUgc2VudGVuY2UgaXMgaXJyZWxldmFudCAoaS5lLiAmbGRxdW87dXZpamVrIGplZGVtIHNhcm11JnJkcXVvOyBhbmQgJmxkcXVvO2plZGVtIHNhcm11IHV2aWplayZyZHF1bzsgYXJlIGVxdWFsIHNlbnRlbmNlcykuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDI1KSwgdGhlIG51bWJlciBvZiB3b3JkcyBpbiB0aGUgZGljdGlvbmFyeS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgd29yZCBmcm9tIHRoZSBkaWN0aW9uYXJ5LCBpdHMgbGVuZ3RoIG5vdCBleGNlZWRpbmcgMTAwLiBBbGwgdGhlIHdvcmRzIGZyb20gdGhlIGRpY3Rpb25hcnkgYXJlIGdvaW5nIHRvIGJlIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgZnJvbSB0aGUgdGFzay4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkFsbCB3b3JkcyBidXQgdGhlIHdvcmQgJmxkcXVvO2EmcmRxdW87IG11c3QgYmUgdXNlZCBpbiB0aGUgdGVzdCBzZW50ZW5jZSBiZWNhdXNlIGVhY2ggd29yZCBjb250YWlucyBhIGxldHRlciB0aGF0IGNhbm5vdCBiZSBmb3VuZCBpbiBhbnkgb3RoZXIgd29yZC4gVGhlcmVmb3JlLCB0aGVyZSBhcmUgdHdvIHBvc3NpYmxlIHNvbHV0aW9ucy4gVGhlIGZpcnN0IG9uZSBiZWluZyB0aGUgc2VudGVuY2Ugd2hpY2ggY29uc2lzdHMgb2YgYWxsIHRoZSB3b3JkcyBhbmQgdGhlIHNlY29uZCBvbmUgYmVpbmcgdGhlIHNlbnRlbmNlIHdoaWNoIGNvbnNpc3RzIG9mIGFsbCB0aGUgd29yZHMgYXBhcnQgZnJvbSB0aGUgd29yZCAmbGRxdW87YSZyZHF1bzsuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=