시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 130 21 20 33.898%

문제

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

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

상근이와 선영이는 메시지를 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+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2Mga1x1YWMxY1x1Yzc1OCBcdWFlMDBcdWM3OTBcdWM1MjkgXHViZTE0XHViODVkXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVhYzAxIFx1YmUxNFx1Yjg1ZFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVhZTAwXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWMyMWNcdWMxMWNcdWI5N2MgXHViYzE0XHVhZmI4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWNkMWQgayFcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzQgXHVjOTExIFx1ZDU1YyBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVhY2U4XHViNzdjXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWJlMTRcdWI4NWRcdWM1ZDAgXHViM2Q5XHVjNzdjXHVkNTU4XHVhYzhjIFx1YzgwMVx1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVjNTU0XHVkNjM4XHVkMGE0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBzZWNyZXRcdWM3NDQgXHVjNTU0XHVkNjM4XHVkMGE0ICg1MTQzNjIpXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM1NTRcdWQ2MzhcdWQ2NTRcdWQ1NWMgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWJlMTRcdWI4NWRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IDZcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva2V5c2VjcmV0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzM3B4OyB3aWR0aDoyNDZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHViZTE0XHViODVkXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjNjNCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1ZDNjOVx1YmIzOFx1YWNmYyBcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YWMxOVx1YWNlMCwgXHVhZTM4XHVjNzc0XHViMjk0IFx1ZDU2ZFx1YzBjMSBrXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjYxMCwgXHViYWE4XHViNGUwIFx1YmUxNFx1Yjg1ZFx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVjNTU0XHVkNjM4XHVkMGE0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM1NTRcdWQ2MzhcdWQ2NTQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzYzlcdWJiMzggTVx1YWNmYyBcdWM1NTRcdWQ2MzhcdWJiMzggQywgXHVhZGY4XHViOWFjXHVhY2UwIFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWQwNmNcdWFlMzAga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBNXHVjNzQ0IENcdWI4NWMgXHVjNTU0XHVkNjM4XHVkNjU0XHVkNTU4XHViMjk0IFx1YzU1NFx1ZDYzOFx1ZDBhNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzEzOCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViZTE0XHViODVkXHVjNzU4IFx1ZDA2Y1x1YWUzMCBrLCBcdWQzYzlcdWJiMzggTSwgXHVjNTU0XHVkNjM4XHViYjM4IENcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBrXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWFjZTAsIE1cdWFjZmMgQ1x1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVjNzc0XHViMmU0LiBNXHVhY2ZjIENcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YWMxOVx1YWNlMCwgTVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQga1x1Yzc1OCBcdWJjMzBcdWMyMThcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNTU0XHVkNjM4XHVkMGE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzU1NFx1ZDYzOFx1ZDBhNFx1Yzc1OCBcdWMyMThcdWIyOTQgMjxzdXA+NjM8XC9zdXA+LTFcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBNXHVjNWQwXHVjMTFjIENcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY1MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktleSBJbnNpZ2h0IiwiZGVzY3JpcHRpb24iOiI8cD5BbGljZSBhbmQgQm9iIGxvdmUgdG8gc2VuZCBlYWNoIG90aGVyIG1lc3NhZ2VzLCBidXQgdGhleSBkb24mcnNxdW87dCBsaWtlIGl0IHdoZW4gb3RoZXIgcGVvcGxlIHJlYWQgdGhlaXIgbWVzc2FnZXMuIFlvdXIgZnJpZW5kIENoYXJsZXMgaXMgdmVyeSBpbnRlcmVzdGVkIGluIHdoYXQgQWxpY2UgYW5kIEJvYiBzZW5kIHRvIGVhY2ggb3RoZXIsIGJ1dCBzaW5jZSBBbGljZSBhbmQgQm9iIGFyZSBlbmNyeXB0aW5nIHRoZWlyIG1lc3NhZ2VzIGhlIGlzIHVuYWJsZSB0byByZWFkIHRoZW0sIGV2ZW4gdGhvdWdoIGhlIGlzIGFibGUgdG8gaW50ZXJjZXB0IHRoZSBlbmNyeXB0ZWQgbWVzc2FnZXMgKGNhbGxlZCAmbGRxdW87Y2lwaGVydGV4dCZyZHF1bzspLjxcL3A+XHJcblxyXG48cD5SZWNlbnRseSwgQ2hhcmxlcyBoYXMgbm90IG9ubHkgaW50ZXJjZXB0ZWQgYW4gZW5jcnlwdGVkIG1lc3NhZ2UsIGhlIGFsc28ga25vd3MgdGhlIG9yaWdpbmFsIGNvbnRlbnQgb2YgdGhpcyBtZXNzYWdlICh3aGljaCBpcyBjYWxsZWQgJmxkcXVvO3BsYWludGV4dCZyZHF1bzspLiBUbyBoZWxwIGhpbSBkZWNyeXB0IGZ1dHVyZSBtZXNzYWdlcyBiZXR3ZWVuIEFsaWNlIGFuZCBCb2IsIHlvdSBhcmUgYXNrZWQgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBoZWxwIGhpbSBsb29rIGZvciB0aGUgZW5jcnlwdGlvbiBrZXkuPFwvcD5cclxuXHJcbjxwPkNoYXJsZXMgaGFzIGluZm9ybWVkIHlvdSB0aGF0IGhlIGtub3dzIHRoYXQgQWxpY2UgYW5kIEJvYiBhcmUgdXNpbmcgYSB0cmFuc3Bvc2l0aW9uIGJsb2NrIGNpcGhlci4gVGhpcyBtZWFucyB0aGF0IGZvciBlYWNoIGJsb2NrIG9mIGsgY2hhcmFjdGVycyBpbiB0aGUgbWVzc2FnZSwgdGhlIGNoYXJhY3RlcnMgd2l0aGluIHRoZSBibG9jayBhcmUgcmUtb3JkZXJlZCBpbnRvIG9uZSBvZiBrISBwb3NzaWJsZSBwZXJtdXRhdGlvbnMgZHVyaW5nIGVuY3J5cHRpb24uIEVhY2ggcGVybXV0YXRpb24gaXMgZGV0ZXJtaW5lZCBieSBpdHMgdW5pcXVlIGNvcnJlc3BvbmRpbmcgZW5jcnlwdGlvbiBrZXkuIFRoZSBrZXkgY29ycmVzcG9uZGluZyB0byB0aGUgcGVybXV0YXRpb24gc2hvd24gaW4gRmlndXJlIDEgd291bGQgYmUgc29tZSByZXByZXNlbnRhdGlvbiBvZiAoMTIzNDU2KSAtJmd0OyAoNTE0MzYyKS4gU2luY2UgeW91ciBvbmx5IHRhc2sgaXMgY291bnRpbmcgKHBvc3NpYmxlKSBrZXlzLCB0aGUgYWN0dWFsIHJlcHJlc2VudGF0aW9uIGlzIG5vdCByZWxldmFudC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rZXlzZWNyZXQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMzcHg7IHdpZHRoOjI0NnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBFeGFtcGxlIG9mIHRyYW5zcG9zaXRpb248XC9wPlxyXG5cclxuPHA+Rm9ydHVuYXRlbHksIENoYXJsZXMgZG9lcyBrbm93IHRoZSBibG9jayBzaXplIGssIGFuZCBoZSBrbm93cyB0aGF0IHRoZSBwbGFpbnRleHQgYW5kIGNpcGhlcnRleHQgdGhhdCBoZSBpbnRlcmNlcHRlZCBjb25zaXN0IG9mIG9uZSBvciBtb3JlIGZ1bGwgYmxvY2tzIG9mIGxlbmd0aCBrIChpLmUuLCBubyBpbmNvbXBsZXRlIGJsb2NrcykgdGhhdCBoYXZlIGVhY2ggYmVlbiBlbmNyeXB0ZWQgd2l0aCB0aGUgc2FtZSBrZXkuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBwbGFpbnRleHQgTSBhbmQgY2lwaGVydGV4dCBDIHRoYXQgQ2hhcmxlcyBoYXMgaW50ZXJjZXB0ZWQsIHlvdXIgcHJvZ3JhbSB3aWxsIGNvbXB1dGUgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBlbmNyeXB0aW9uIGtleXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBpbnB1dCBjb250YWlucyB0aHJlZSBsaW5lczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSBjb250YWluaW5nIGEgcG9zaXRpdmUgaW50ZWdlciBrLCB0aGUgYmxvY2sgc2l6ZSAoayAmZ2U7IDEpLjxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSBjb250YWluaW5nIE0sIHRoZSBwbGFpbnRleHQgKDEgJmxlOyB8TXwgJmxlOyAxMDAsIHxNfCBpcyBhIG11bHRpcGxlIG9mIGspLjxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSBjb250YWluaW5nIEMsIHRoZSBjaXBoZXJ0ZXh0ICh8Q3wgPSB8TXwpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Qm90aCBwbGFpbnRleHQgYW5kIGNpcGhlcnRleHQgY29uc2lzdCBvbmx5IG9mIGxvd2VyLWNhc2UgbGV0dGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBlbmNyeXB0aW9uIGtleXMgb2Ygc2l6ZSBrLiBUaGlzIG51bWJlciB3aWxsIG5vdCBleGNlZWQgMjxzdXA+NjM8XC9zdXA+LTEuIElmIGl0IGlzIGltcG9zc2libGUgdG8gb2J0YWluIE0gZnJvbSBDIGJ5IGEgdHJhbnNwb3NpdGlvbiBjaXBoZXIgb2YgYmxvY2sgc2l6ZSBrLCBwcmludCAmbHNxdW87MCZyc3F1bzsgKHRoZSBudW1iZXIgemVybykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2012 K번

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