K - 密钥洞察

Alice 和 Bob 喜欢互相发送消息，但他们不喜欢别人阅读这些消息。你的朋友 Charles 对 Alice 和 Bob 互相发送的内容非常感兴趣，但由于 Alice 和 Bob 对他们的消息进行了加密，即使 Charles 能够拦截到加密后的消息（称为“密文”），他也无法阅读。

图 1：置换示例。

最近，Charles 不仅拦截了一条加密消息，他还知道了这条消息的原始内容（称为“明文”）。为了帮助他解密 Alice 和 Bob 之间未来的消息，你需要编写一个程序来帮助他寻找加密密钥。

Charles 告知你，他知道 Alice 和 Bob 使用的是置换分组密码。这意味着对于消息中的每一个长度为 $k$ 的字符块，块内的字符在加密过程中会被重新排列为 $k!$ 种可能的置换之一。每一种置换由其唯一对应的加密密钥决定。图 1 中所示置换对应的密钥将是 $(123456) \to (514362)$ 的某种表示。由于你唯一的任务是计算（可能的）密钥数量，因此具体的表示形式并不重要。

幸运的是，Charles 确实知道块大小 $k$，并且他知道他拦截的明文和密文由一个或多个长度为 $k$ 的完整块组成（即没有不完整的块），且每个块都使用相同的密钥进行加密。

给定 Charles 拦截到的明文 $M$ 和密文 $C$，你的程序需要计算可能的加密密钥数量。

输入格式

对于每个测试用例，输入包含三行：

• 第一行包含一个正整数 $k$，表示块大小 ($k \ge 1$)。
• 第二行包含 $M$，即明文 ($1 \le |M| \le 100$，$|M|$ 是 $k$ 的倍数)。
• 第三行包含 $C$，即密文 ($|C| = |M|$)。

明文和密文均仅由小写字母组成。

输出格式

对于每个测试用例，输出一行，包含大小为 $k$ 的可能加密密钥的数量。该数字不会超过 $2^{63} - 1$。如果无法通过块大小为 $k$ 的置换密码从 $M$ 得到 $C$，则输出“0”（数字零）。

样例

输入 1

4
treewood
ertedowo

输出 1

1

输入 2

1
nwerc
ncrew

输出 2

0

输入 3

6
secret
etrcse

输出 3

2

输入 4

1
impossibru
youdontsay

输出 4

0