암호 해독

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

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

상근이와 선영이는 메시지를 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을 출력한다.