Description:
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$$$.
Input Format:
The 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.
Output Format:
Output a single integer: the number of valid triples $$$(x, y, z)$$$.
Note:
In 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"})$$$.