Фабрика палиндромов

Рассмотрим произвольную строку 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).