Фабрика паліндромів
Розглянемо довільний рядок g. Будемо називати цей рядок генератором паліндромів. Множина паліндромів P(g), які генеруються цим рядком визначаться наступним чином.
Нехай довжина рядка рівна n. Для усіх i від 1 до n в P(g) включаються рядки g[1..i]g[1..i]^r и g[1..i]g[1..i-1]^r, де α^{r }позначає α, записаний у зворотному порядку.
Наприклад, якщо g="olymp", то P(g)={"oo", "o", "ollo", "olo", "olyylo", "olylo", "olymmylo", "olymylo", "olymppmylo", "olympmylo"}.
Для заданого генератора паліндромів g та рядка s потрібно знайти кількість входжень рядків з P(g) у s як підрядків. А саме, потрібно знайти кількість таких пар (i, j), що s[i..j] P(g).
Вхідні дані
Перший рядок вхідного файлу містить рядок g. Другий рядок вхідного файлу містить s. Обидва рядки непорожні і мають довжину не більше 100000 символів.
Вихідні дані
Виведіть у вихідний файл кількість таких пар (i, j), що s[i..j] P(g).