암호 해독

상근이와 선영이는 메시지를 자주 주고받는다. 두 사람은 다른 사람이 자신들의 메시지를 읽는 것을 원하지 않아, 언제나 메시지를 암호화해서 보낸다. 정인이는 두 사람이 주고받는 메시지를 가로채고 있지만, 암호화되어 있어 그 내용을 읽을 수 없다.

최근 정인이는 어떤 메시지의 평문 원본을 우연히 손에 넣었다. 앞으로 가로챌 다른 메시지도 해독하기 위해, 정인이는 사용된 암호키를 알아내려고 한다.

암호화 방식은 다음과 같다. 평문을 앞에서부터 $k$글자씩 블록으로 나눈 뒤, 각 블록 안의 글자 순서를 하나의 순열에 따라 바꾼다. 순서를 바꾸는 방법은 모두 $k!$가지가 있으며, 그중 하나의 순열을 골라 모든 블록에 똑같이 적용한다. 이때 사용한 순열을 암호키라고 한다.

암호키는 $1$부터 $k$까지의 수를 나열해 나타내며, 블록 안 $i$번째 위치의 글자는 암호키의 $i$번째 수가 가리키는 위치로 옮겨진다. 예를 들어 블록 크기가 $6$이고 암호키가 $(5\,1\,4\,3\,6\,2)$이면, 각 글자는 위치 $1\to5,\ 2\to1,\ 3\to4,\ 4\to3,\ 5\to6,\ 6\to2$로 옮겨져 평문 블록 secret은 암호문 etrcse가 된다.

평문과 암호문의 길이는 서로 같고, 그 길이는 항상 $k$로 나누어떨어진다. 모든 블록은 같은 암호키로 암호화된다.

평문 $M$, 암호문 $C$, 블록 크기 $k$가 주어질 때, $M$을 $C$로 암호화하는 암호키의 개수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 줄이며, 첫째 줄에 블록 크기 $k$, 둘째 줄에 평문 $M$, 셋째 줄에 암호문 $C$가 주어진다. $k$는 양의 정수이다. $M$과 $C$는 알파벳 소문자로만 이루어지며, 길이는 최대 $100$이다. $M$과 $C$의 길이는 서로 같고, 그 길이는 $k$의 배수이다. 입력은 파일의 끝까지 계속된다.

각 테스트 케이스마다 가능한 암호키의 개수를 한 줄에 하나씩 출력한다. 암호키의 개수는 $2^{63}-1$을 넘지 않는다. 만약 $M$을 $C$로 암호화할 수 없다면 $0$을 출력한다.