Given two positive integers ~N~ and ~M~, and two strings ~S~ and ~T~ of lowercase letters, we generate two strings ~A~ and ~B~ so that they have the following characteristics:
- ~A~ and ~B~ have equal string length;
- ~A~ is generated by concatenating ~S~ for ~N~ times;
- ~B~ is generated by concatenating ~T~ for ~M~ times.
It is regarded as a match if the ~i~-th character in ~A~ is the same as the ~i~-th character in ~B~. Given ~N,M,S,T~, please write a program to return the number of matches among ~A~ and ~B~.
The first line of the input contains 2 integers, representing ~N~ and ~M~, separated by a space.
The second and third line contain string ~S~ and ~T~, respectively.
It is guaranteed that ~A~ and ~B~ have equal string length.
- In ~20\%~ of the test cases, the length of ~A \le 10^5~.
- In ~40\%~ of the test cases, the length of ~S \le 10~ and the length of ~T \le 10~.
- In ~100\%~ of the test cases, ~N,M \le 10^9~, the length of ~S \le 10^6~, the length of ~T \le 10^6~.
Print the number of matches among ~A~ and ~B~.
Sample Input 1
3 5 ababa aba
Sample Output 1
Explanation for Sample 1
~A =~ ababaababaababa, ~B =~ abaabaabaabaaba. Hence, ~A_i = B_i~ when ~i = 1,2,3,6,10,13,14,15~.
Sample Input 2
30 20 abbb bbaabb
Sample Output 2