CF1909G Pumping Lemma

有两个只含小写字母的字符串 $s$ 和 $t$，长度分别为 $n$ 和 $m$。 请计算满足下列要求的字符串三元组 $(x,y,z)$ 有几个： - $s=x+y+z$ （$+$ 代表连接）； - $t = x+\underbrace{ y+\dots+y }_{k \text{ 个}} + z$，其中 $k$ 为整数。

第一行两个整数 $n,m(1 \le n < m \le 10^7)$。 第二行一个字符串 $s$。 第三行一个字符串 $t$。

一行，一个整数表示答案。

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"}) $ .