E :: Key Insight

Time Limit: 1 Second    Memory Limit: 32768 KB

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.

Input

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.

 

Output

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).

 

Sample Input

4 
treewood 
ertedowo 
1 
nwerc 
ncrew 
6 
secret 
etrcse 
1 
impossibru 
youdontsay

Sample Output

1
0
2
0
Submit

Source: NWERC 2012