Вам даны две строки \(s\), \(t\) длины \(n\), \(m\), соответственно. Обе строки состоят из строчных букв латинского алфавита.
Подсчитайте тройки \((x, y, z)\) строк, для которых справедливы следующие условия:
- \(s = x+y+z\) (символ \(+\) обозначает конкатенацию);
- \(t = x+\underbrace{ y+\dots+y }_{k \text{ раз}} + z\) для некоторого целого числа \(k\).
Выходные данные
Выведите одно целое число: количество допустимых троек \((x, y, z)\).
Примечание
В первом наборе входных данных единственной подходящей тройкой является \((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"})\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 8
abcd
abcbcbcd
|
1
|
|
2
|
3 5
aaa
aaaaa
|
5
|
|
3
|
12 16
abbababacaab
abbababababacaab
|
8
|