Tanchiky & 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$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \lt 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

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

Pumping Lemma

Examples