G. Лемма о накачке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
Tanchiky & Siromaru - Crystal Gravity
⠀

Вам даны две строки $$$s$$$, $$$t$$$ длины $$$n$$$, $$$m$$$, соответственно. Обе строки состоят из строчных букв латинского алфавита.

Подсчитайте тройки $$$(x, y, z)$$$ строк, для которых справедливы следующие условия:

  • $$$s = x+y+z$$$ (символ $$$+$$$ обозначает конкатенацию);
  • $$$t = x+\underbrace{ y+\dots+y }_{k \text{ раз}} + z$$$ для некоторого целого числа $$$k$$$.
Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n < m \leq 10^7$$$) — длины строк $$$s$$$ и $$$t$$$, соответственно.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.

Третья строка содержит строку $$$t$$$ длины $$$m$$$, состоящую из строчных латинских букв.

Выходные данные

Выведите одно целое число: количество допустимых троек $$$(x, y, z)$$$.

Примеры
Входные данные
4 8
abcd
abcbcbcd
Выходные данные
1
Входные данные
3 5
aaa
aaaaa
Выходные данные
5
Входные данные
12 16
abbababacaab
abbababababacaab
Выходные данные
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"})$$$.