Description

[丛雨]和[芳乃]准备了两张白纸，丛雨在第一张纸上写一个整数 $N$ 和一个由小写字母组成的字符串 $S$ ，将 $S$ 重复 $N$ 次后产生一个更长的字符串 $A$ 。相应的，芳乃在另一张纸上写一个整数 $M$ 和一个由小写字母组成的字符串 $T$ ，接着她把 $T$ 重复 $M$ 次产生字符串 $B$ 。并且保证字符串 $A$ 和 $B$ 的长度相等；这时候，如果 $A$ 中的第 $i$ 个字符与 $B$ 中的第 $i$ 个字符相同，则称为字符配对成功。给定 $N$ 、$M$ 、 $S$ 、$T$ ，请计算 $A$ 和 $B$ 的成功配对的字符数。

Format

Input

第一行两个用空格整数 $N$ 和 $M$ 。

第二行和第三行分别为 $S$ 和 $T$ 。

数据保证 $A$ 和 $B$ 的长度相等。

Output

输出为一个整数，表示 $A$ 和 $B$ 匹配成功的字符数。

Samples

30 20
abbb
bbaabb

70

Limitation

对于 $40\%$ 的数据，满足 $A \le 10^5$ 。

对于再 $30\%$ 的数据，满足 $|S|,|T| \le 10$　（ $|S|$ 表示 $S$ 的长度）。

对于 $100\%$ 的数据，满足 $N, M \le 10^9,\ |S|,|T| \le 10^6$ ，保证 $A$ 和 $B$ 的长度相等。

1s, 128MB for each test case.