给定两个字符串 $$$s$$$、$$$t$$$,长度分别为 $$$n$$$、$$$m$$$。两个字符串均由英文字母表中的小写字母组成。
计算字符串的三元组 $$$(x, y, z)$$$ ,使得以下条件成立:
- $$$s = x+y+z$$$(符号$$$+$$$表示串联);
- $$$t = x+\underbrace{ y+\dots+y }_{k \text{ times}} + z$$$ 对于某个整数 $$$k$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n < m \leq 10^7$$$) - 分别是字符串 $$$s$$$ 和 $$$t$$$ 的长度。
第二行包含长度为$$$n$$$的字符串$$$s$$$,由英文字母的小写字母组成。
第三行包含长度为$$$m$$$的字符串$$$t$$$,由英文字母的小写字母组成。
输出
输出单个整数:有效三元组 $$$(x, y, z)$$$ 的数量。
示例
输入 #1
4 8 abcd abcbcbcd
输出 #1
1
输入 #2
3 5 aaa aaaaa
输出 #2
5
输入 #3
12 16 abbababacaab abbababababacaab
输出 #3
8
注意
在第一个测试用例中,唯一有效的三元组是 $$$(x, y, z) = (\texttt{"a"}, \texttt{"bc"}, \texttt{"d"})$$$。事实上,
- $$$\texttt{"abcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"d"}$$$;
- $$$\texttt{"abcbcbcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"d"}$$$。
在第二个测试用例中,有 $$$5$$$ 有效三元组:
- $$$(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{""})$$$。
在第三个测试用例中,有 $$$8$$$ 有效三元组:
- $$$(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"})$$$。