Breaking the Cipher

Sanggeun and Sunyoung exchange messages often. Because they don't want anyone else to read what they write, they always encrypt their messages before sending them. Jeongin intercepts the messages they exchange, but since the messages are encrypted, Jeongin cannot read their contents.

Recently, Jeongin happened to obtain the original plaintext of one message. In order to decrypt other intercepted messages in the future, Jeongin wants to determine the key that was used.

The encryption works as follows. The plaintext is split from the left into blocks of $k$ characters. Within each block, the characters are reordered according to a single permutation. There are $k!$ possible permutations; one of them is chosen and applied identically to every block. The permutation chosen this way is called the key.

A key is written as an arrangement of the numbers $1$ through $k$: the character at position $i$ within a block is moved to the position indicated by the $i$-th number of the key. For example, if the block size is $6$ and the key is $(5,1,4,3,6,2)$, then the characters move as $1\to5,\ 2\to1,\ 3\to4,\ 4\to3,\ 5\to6,\ 6\to2$, so the plaintext block secret becomes the ciphertext etrcse.

The plaintext and the ciphertext always have the same length, and that length is always divisible by $k$. Every block is encrypted with the same key.

Given the plaintext $M$, the ciphertext $C$, and the block size $k$, write a program that counts how many keys encrypt $M$ into $C$.

The input consists of several test cases. Each test case spans three lines: the block size $k$ on the first line, the plaintext $M$ on the second, and the ciphertext $C$ on the third. $k$ is a positive integer. $M$ and $C$ consist only of lowercase letters and are at most $100$ characters long. $M$ and $C$ have the same length, and that length is a multiple of $k$. The input continues until the end of the file.

For each test case, print the number of possible keys, one per line. This count never exceeds $2^{63}-1$. If $M$ cannot be encrypted into $C$, print $0$.