G. Pumping Lemmatime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputTanchiky & Siromaru - Crystal Gravity⠀You are given two strings s, t of length n, m, respectively. Both strings consist of lowercase letters of the English alphabet.Count the triples (x, y, z) of strings such that the following conditions are true:  s = x+y+z (the symbol + represents the concatenation);  t = x+\underbrace{ y+\dots+y }_{k \text{ times}} + z for some integer k. InputThe first line contains two integers n and m (1 \leq n < m \leq 10^7) — the length of the strings s and t, respectively.The second line contains the string s of length n, consisting of lowercase letters of the English alphabet.The third line contains the string t of length m, consisting of lowercase letters of the English alphabet.OutputOutput a single integer: the number of valid triples (x, y, z).ExamplesInput
4 8abcdabcbcbcdOutput
1
Input
3 5aaaaaaaaOutput
5
Input
12 16abbababacaababbababababacaabOutput
8
NoteIn the first test case, the only valid triple is (x, y, z) = (\texttt{"a"}, \texttt{"bc"}, \texttt{"d"}). In fact,   \texttt{"abcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"d"};  \texttt{"abcbcbcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"d"}. In the second test case, there are 5 valid triples:   (x, y, z) = (\texttt{""}, \texttt{"a"}, \texttt{"aa"});  (x, y, z) = (\texttt{""}, \texttt{"aa"}, \texttt{"a"});  (x, y, z) = (\texttt{"a"}, \texttt{"a"}, \texttt{"a"});  (x, y, z) = (\texttt{"a"}, \texttt{"aa"}, \texttt{""});  (x, y, z) = (\texttt{"aa"}, \texttt{"a"}, \texttt{""}). In the third test case, there are 8 valid triples:   (x, y, z) = (\texttt{"ab"}, \texttt{"ba"}, \texttt{"babacaab"});  (x, y, z) = (\texttt{"abb"}, \texttt{"ab"}, \texttt{"abacaab"});  (x, y, z) = (\texttt{"abba"}, \texttt{"ba"}, \texttt{"bacaab"});  (x, y, z) = (\texttt{"ab"}, \texttt{"baba"}, \texttt{"bacaab"});  (x, y, z) = (\texttt{"abbab"}, \texttt{"ab"}, \texttt{"acaab"});  (x, y, z) = (\texttt{"abb"}, \texttt{"abab"}, \texttt{"acaab"});  (x, y, z) = (\texttt{"abbaba"}, \texttt{"ba"}, \texttt{"caab"});  (x, y, z) = (\texttt{"abba"}, \texttt{"baba"}, \texttt{"caab"}). 
4 8abcdabcbcbcd
1 
['hashing', 'strings', '*3000']