E. Конкатенация с пересечением
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи было три строки $$$a$$$, $$$b$$$ и $$$s$$$, состоящие из строчных символов латинского алфавита. Длины строк $$$a$$$ и $$$b$$$ равны $$$n$$$, длина строки $$$s$$$ равна $$$m$$$.

Вася решил выбрать подстроку из строки $$$a$$$, затем выбрать подстроку из строки $$$b$$$ и сконцентрировать их. Формально, он выбирает подотрезок $$$[l_1, r_1]$$$ ($$$1 \leq l_1 \leq r_1 \leq n$$$) и подотрезок $$$[l_2, r_2]$$$ ($$$1 \leq l_2 \leq r_2 \leq n$$$), а после конкатенации получает строку $$$a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2}$$$.

Теперь Васю заинтересовал вопрос, сколькими способами он может выбрать пару отрезков так, что выполнены следующие условия:

  • отрезки $$$[l_1, r_1]$$$ и $$$[l_2, r_2]$$$ пересекаются, то есть существует хотя бы одно целое число $$$x$$$, такое что $$$l_1 \leq x \leq r_1$$$ и $$$l_2 \leq x \leq r_2$$$;
  • полученная Васей в итоге строка $$$a[l_1, r_1] + b[l_2, r_2]$$$ равна строке $$$s$$$.
Входные данные

Первая строка содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 500\,000, 2 \leq m \leq 2 \cdot n$$$) — длина строк $$$a$$$ и $$$b$$$ и длина строки $$$s$$$.

Следующие три строки содержат строки $$$a$$$, $$$b$$$ и $$$s$$$ соответственно. Длина строк $$$a$$$ и $$$b$$$ составляет $$$n$$$, а длина строки $$$s$$$ — $$$m$$$.

Все строки состоят из строчных английских букв.

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

Выведите одно целое число — количество способов выбрать пару отрезков, удовлетворяющую Васиным условиям.

Примеры
Входные данные
6 5
aabbaa
baaaab
aaaaa
Выходные данные
4
Входные данные
5 4
azaza
zazaz
azaz
Выходные данные
11
Входные данные
9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz
Выходные данные
2
Примечание

Перечислим все пары отрезков, которые мог выбрать Вася в первом примере:

  1. $$$[2, 2]$$$ и $$$[2, 5]$$$;
  2. $$$[1, 2]$$$ и $$$[2, 4]$$$;
  3. $$$[5, 5]$$$ и $$$[2, 5]$$$;
  4. $$$[5, 6]$$$ и $$$[3, 5]$$$;