시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 124 18 18 36.000%

문제

상근이와 선영이는 메시지를 자주 주고 받는다. 하지만, 그들은 다른 사람이 자신이 작성한 메시지를 읽는 것을 매우 싫어한다. 정인이는 이 두 사람이 서로 보내는 메시지에 큰 관심을 가지고 있고, 메시지를 가로채고 있다. 하지만, 상근이와 선영이는 메시지를 암호화 하기 때문에 정인이는 메시지를 읽을 수 없다. 정인이가 가로채는 메시지는 암호화된 메시지(암호문)이다.

최근에 정인이는 우연히 메시지 원본(평문)을 얻었다. 정인이는 다른 메시지도 해독하기 위해서 암호키를 찾기로 했다.

상근이와 선영이는 메시지를 k개의 글자씩 블럭으로 나눈 다음에 각 블럭에 들어있는 글자의 순서를 바꾸는 것이다. 순서를 바꾸는 방법은 총 k!가지가 있으며, 이 중 한 순열을 골라서 모든 블럭에 동일하게 적용한다. 이 때 사용한 순열을 암호키라고 한다. 아래 그림은 secret을 암호키 (514362)를 이용해서 암호화한 것이고, 블럭의 크기는 6이다.

정인이는 블럭의 크기도 알고 있다. 또, 평문과 암호문의 길이는 같고, 길이는 항상 k로 나누어 떨어진다. 또, 모든 블럭은 같은 암호키를 이용해서 암호화 한다.

평문 M과 암호문 C, 그리고 블럭의 크기 k가 주어졌을 때, M을 C로 암호화하는 암호키의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있따. 각 테스트 케이스는 세 줄로 이루어져 있고, 블럭의 크기 k, 평문 M, 암호문 C가 한 줄에 하나씩 주어진다. k는 1보다 큰 양의 정수이고, M과 C는 알파벳 소문자로만 이루어져 있으며, 길이는 최대 100이다. M과 C의 길이는 같고, M의 길이는 k의 배수이다. 

출력

각 테스트 케이스에 대해서, 가능한 암호키의 개수를 출력한다. 암호키의 수는 263-1을 넘지 않는다. 만약, M에서 C를 만들 수 없다면 0을 출력한다.

예제 입력 1

4
treewood
ertedowo
6
secret
etrcse
1
impossibru
youdontsay

예제 출력 1

1
2
0

힌트

W3sicHJvYmxlbV9pZCI6IjM2NTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWQ2MzggXHVkNTc0XHViM2M1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWM3OTBcdWM4ZmMgXHVjOGZjXHVhY2UwIFx1YmMxYlx1YjI5NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFkZjhcdWI0ZTRcdWM3NDAgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNzkxXHVjMTMxXHVkNTVjIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWM3N2RcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjllNFx1YzZiMCBcdWMyZWJcdWM1YjRcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM3NzQgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMxMWNcdWI4NWMgXHViY2Y0XHViMGI0XHViMjk0IFx1YmE1NFx1YzJkY1x1YzljMFx1YzVkMCBcdWQwNzAgXHVhZDAwXHVjMmVjXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWFjMDBcdWI4NWNcdWNjNDRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVjNzdkXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWI4NWNcdWNjNDRcdWIyOTQgXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IFx1YzU1NFx1ZDYzOFx1ZDY1NFx1YjQxYyBcdWJhNTRcdWMyZGNcdWM5YzAoXHVjNTU0XHVkNjM4XHViYjM4KVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVhZGZjXHVjNWQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM2YjBcdWM1ZjBcdWQ3ODggXHViYTU0XHVjMmRjXHVjOWMwIFx1YzZkMFx1YmNmOChcdWQzYzlcdWJiMzgpXHVjNzQ0IFx1YzViYlx1YzVjOFx1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YjJlNFx1Yjk3OCBcdWJhNTRcdWMyZGNcdWM5YzBcdWIzYzQgXHVkNTc0XHViM2M1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM1NTRcdWQ2MzhcdWQwYTRcdWI5N2MgXHVjYzNlXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2Mga1x1YWMxY1x1Yzc1OCBcdWFlMDBcdWM3OTBcdWM1MjkgXHViZTE0XHViN2VkXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVhYzAxIFx1YmUxNFx1YjdlZFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVhZTAwXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWMyMWNcdWMxMWNcdWI5N2MgXHViYzE0XHVhZmI4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWNkMWQgayFcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzQgXHVjOTExIFx1ZDU1YyBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVhY2U4XHViNzdjXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWJlMTRcdWI3ZWRcdWM1ZDAgXHViM2Q5XHVjNzdjXHVkNTU4XHVhYzhjIFx1YzgwMVx1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YyBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YzU1NFx1ZDYzOFx1ZDBhNFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgc2VjcmV0XHVjNzQ0IFx1YzU1NFx1ZDYzOFx1ZDBhNCAoNTE0MzYyKVx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNTU0XHVkNjM4XHVkNjU0XHVkNTVjIFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHViZTE0XHViN2VkXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCA2XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tleXNlY3JldC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzNweDsgd2lkdGg6MjQ2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YmUxNFx1YjdlZFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIzYzQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWQzYzlcdWJiMzhcdWFjZmMgXHVjNTU0XHVkNjM4XHViYjM4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWFjMTlcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWQ1NmRcdWMwYzEga1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHViNWE4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWI2MTAsIFx1YmFhOFx1YjRlMCBcdWJlMTRcdWI3ZWRcdWM3NDAgXHVhYzE5XHVjNzQwIFx1YzU1NFx1ZDYzOFx1ZDBhNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNTU0XHVkNjM4XHVkNjU0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2M5XHViYjM4IE1cdWFjZmMgXHVjNTU0XHVkNjM4XHViYjM4IEMsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWJlMTRcdWI3ZWRcdWM3NTggXHVkMDZjXHVhZTMwIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgTVx1Yzc0NCBDXHViODVjIFx1YzU1NFx1ZDYzOFx1ZDY1NFx1ZDU1OFx1YjI5NCBcdWM1NTRcdWQ2MzhcdWQwYTRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViNTMwLiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMxMzggXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YmUxNFx1YjdlZFx1Yzc1OCBcdWQwNmNcdWFlMzAgaywgXHVkM2M5XHViYjM4IE0sIFx1YzU1NFx1ZDYzOFx1YmIzOCBDXHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4ga1x1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwLCBNXHVhY2ZjIENcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDEwMFx1Yzc3NFx1YjJlNC4gTVx1YWNmYyBDXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWFjMTlcdWFjZTAsIE1cdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IGtcdWM3NTggXHViYzMwXHVjMjE4XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzU1NFx1ZDYzOFx1ZDBhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM1NTRcdWQ2MzhcdWQwYTRcdWM3NTggXHVjMjE4XHViMjk0IDI8c3VwPjYzPFwvc3VwPi0xXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgTVx1YzVkMFx1YzExYyBDXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLZXkgSW5zaWdodCIsImRlc2NyaXB0aW9uIjoiPHA+QWxpY2UgYW5kIEJvYiBsb3ZlIHRvIHNlbmQgZWFjaCBvdGhlciBtZXNzYWdlcywgYnV0IHRoZXkgZG9uJnJzcXVvO3QgbGlrZSBpdCB3aGVuIG90aGVyIHBlb3BsZSByZWFkIHRoZWlyIG1lc3NhZ2VzLiBZb3VyIGZyaWVuZCBDaGFybGVzIGlzIHZlcnkgaW50ZXJlc3RlZCBpbiB3aGF0IEFsaWNlIGFuZCBCb2Igc2VuZCB0byBlYWNoIG90aGVyLCBidXQgc2luY2UgQWxpY2UgYW5kIEJvYiBhcmUgZW5jcnlwdGluZyB0aGVpciBtZXNzYWdlcyBoZSBpcyB1bmFibGUgdG8gcmVhZCB0aGVtLCBldmVuIHRob3VnaCBoZSBpcyBhYmxlIHRvIGludGVyY2VwdCB0aGUgZW5jcnlwdGVkIG1lc3NhZ2VzIChjYWxsZWQgJmxkcXVvO2NpcGhlcnRleHQmcmRxdW87KS48XC9wPlxyXG5cclxuPHA+UmVjZW50bHksIENoYXJsZXMgaGFzIG5vdCBvbmx5IGludGVyY2VwdGVkIGFuIGVuY3J5cHRlZCBtZXNzYWdlLCBoZSBhbHNvIGtub3dzIHRoZSBvcmlnaW5hbCBjb250ZW50IG9mIHRoaXMgbWVzc2FnZSAod2hpY2ggaXMgY2FsbGVkICZsZHF1bztwbGFpbnRleHQmcmRxdW87KS4gVG8gaGVscCBoaW0gZGVjcnlwdCBmdXR1cmUgbWVzc2FnZXMgYmV0d2VlbiBBbGljZSBhbmQgQm9iLCB5b3UgYXJlIGFza2VkIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgaGVscCBoaW0gbG9vayBmb3IgdGhlIGVuY3J5cHRpb24ga2V5LjxcL3A+XHJcblxyXG48cD5DaGFybGVzIGhhcyBpbmZvcm1lZCB5b3UgdGhhdCBoZSBrbm93cyB0aGF0IEFsaWNlIGFuZCBCb2IgYXJlIHVzaW5nIGEgdHJhbnNwb3NpdGlvbiBibG9jayBjaXBoZXIuIFRoaXMgbWVhbnMgdGhhdCBmb3IgZWFjaCBibG9jayBvZiBrIGNoYXJhY3RlcnMgaW4gdGhlIG1lc3NhZ2UsIHRoZSBjaGFyYWN0ZXJzIHdpdGhpbiB0aGUgYmxvY2sgYXJlIHJlLW9yZGVyZWQgaW50byBvbmUgb2YgayEgcG9zc2libGUgcGVybXV0YXRpb25zIGR1cmluZyBlbmNyeXB0aW9uLiBFYWNoIHBlcm11dGF0aW9uIGlzIGRldGVybWluZWQgYnkgaXRzIHVuaXF1ZSBjb3JyZXNwb25kaW5nIGVuY3J5cHRpb24ga2V5LiBUaGUga2V5IGNvcnJlc3BvbmRpbmcgdG8gdGhlIHBlcm11dGF0aW9uIHNob3duIGluIEZpZ3VyZSAxIHdvdWxkIGJlIHNvbWUgcmVwcmVzZW50YXRpb24gb2YgKDEyMzQ1NikgLSZndDsgKDUxNDM2MikuIFNpbmNlIHlvdXIgb25seSB0YXNrIGlzIGNvdW50aW5nIChwb3NzaWJsZSkga2V5cywgdGhlIGFjdHVhbCByZXByZXNlbnRhdGlvbiBpcyBub3QgcmVsZXZhbnQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva2V5c2VjcmV0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzM3B4OyB3aWR0aDoyNDZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMTogRXhhbXBsZSBvZiB0cmFuc3Bvc2l0aW9uPFwvcD5cclxuXHJcbjxwPkZvcnR1bmF0ZWx5LCBDaGFybGVzIGRvZXMga25vdyB0aGUgYmxvY2sgc2l6ZSBrLCBhbmQgaGUga25vd3MgdGhhdCB0aGUgcGxhaW50ZXh0IGFuZCBjaXBoZXJ0ZXh0IHRoYXQgaGUgaW50ZXJjZXB0ZWQgY29uc2lzdCBvZiBvbmUgb3IgbW9yZSBmdWxsIGJsb2NrcyBvZiBsZW5ndGggayAoaS5lLiwgbm8gaW5jb21wbGV0ZSBibG9ja3MpIHRoYXQgaGF2ZSBlYWNoIGJlZW4gZW5jcnlwdGVkIHdpdGggdGhlIHNhbWUga2V5LjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgcGxhaW50ZXh0IE0gYW5kIGNpcGhlcnRleHQgQyB0aGF0IENoYXJsZXMgaGFzIGludGVyY2VwdGVkLCB5b3VyIHByb2dyYW0gd2lsbCBjb21wdXRlIHRoZSBudW1iZXIgb2YgcG9zc2libGUgZW5jcnlwdGlvbiBrZXlzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB0aGUgaW5wdXQgY29udGFpbnMgdGhyZWUgbGluZXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgY29udGFpbmluZyBhIHBvc2l0aXZlIGludGVnZXIgaywgdGhlIGJsb2NrIHNpemUgKGsgJmdlOyAxKS48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgY29udGFpbmluZyBNLCB0aGUgcGxhaW50ZXh0ICgxICZsZTsgfE18ICZsZTsgMTAwLCB8TXwgaXMgYSBtdWx0aXBsZSBvZiBrKS48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgY29udGFpbmluZyBDLCB0aGUgY2lwaGVydGV4dCAofEN8ID0gfE18KTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkJvdGggcGxhaW50ZXh0IGFuZCBjaXBoZXJ0ZXh0IGNvbnNpc3Qgb25seSBvZiBsb3dlci1jYXNlIGxldHRlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgcG9zc2libGUgZW5jcnlwdGlvbiBrZXlzIG9mIHNpemUgay4gVGhpcyBudW1iZXIgd2lsbCBub3QgZXhjZWVkIDI8c3VwPjYzPFwvc3VwPi0xLiBJZiBpdCBpcyBpbXBvc3NpYmxlIHRvIG9idGFpbiBNIGZyb20gQyBieSBhIHRyYW5zcG9zaXRpb24gY2lwaGVyIG9mIGJsb2NrIHNpemUgaywgcHJpbnQgJmxzcXVvOzAmcnNxdW87ICh0aGUgbnVtYmVyIHplcm8pLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==