题目描述
Alice and Bob love to send each other messages, but they don’t like it when other people read their messages. Your friend Charles is very interested in what Alice and Bob send to each other, but since Alice and Bob are encrypting their messages he is unable to read them, even though he is able to intercept the encrypted messages (called “ciphertext”).
Recently, Charles has not only intercepted an encrypted message, he also knows the original content of this message (which is called “plaintext”). To help him decrypt future messages between Alice and Bob, you are asked to write a program that will help him look for the encryption key.
Charles has informed you that he knows that Alice and Bob are using a transposition block cipher. This means that for each block of k characters in the message, the characters within the block are re-ordered into one of k! possible permutations during encryption. Each permutation is determined by its unique corresponding encryption key. The key corresponding to the permutation shown in Figure 1 would be some representation of (123456) -> (514362). Since your only task is counting (possible) keys, the actual representation is not relevant.
Fortunately, Charles does know the block size k, and he knows that the plaintext and ciphertext that he intercepted consist of one or more full blocks of length k (i.e., no incomplete blocks) that have each been encrypted with the same key.
Given the plaintext M and ciphertext C that Charles has intercepted, your program will compute the number of possible encryption keys.
输入
For each test case, the input contains three lines:
One line containing a positive integer k, the block size (k >= 1).
One line containing M, the plaintext (1 <= |M| <= 100;|M| is a multiple of k).
One line containing C, the ciphertext (|C| =|M|).
Both plaintext and ciphertext consist only of lower-case letters.
输出
For each test case, print one line containing the number of possible encryption keys of size k.
This number will not exceed 263-1. If it is impossible to obtain M from C by a transposition cipher of block size k, print ‘0’ (the number zero).
样例输入 Copy
4
treewood
ertedowo
1
nwerc
ncrew
6
secret
etrcse
1
impossibru
youdontsay
样例输出 Copy
1
0
2
0