配对 pair

题目描述

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

30 20
abbb
bbaabb

样例输出 #1

70

提示

对于40%的数据，满足A<=10^5。

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

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