На уроке английского языка Никите совсем нечем было заняться, и он вспомнил о замечательных строках под названием палиндромы. Напомним, что строка называется палиндромом, если она читается одинаково слева направо и справа налево. Примеры таких строк: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Никита стал старательно искать все палиндромы в тексте, который они читали в тот момент на уроке. Для каждого вхождения каждого палиндрома он выписывал пару — позицию начала и позицию конца этого вхождения палиндрома в текст. Каждое вхождение каждого палиндрома Никита называет подпалиндромом. Когда Никита нашел все подпалиндромы, ему стало интересно, сколько различных пар из них пересекается. Два подпалиндрома пересекаются, если они содержат общую позицию в тексте, причем считается, что никакой палиндром не пересекается сам с собой.

Рассмотрим на примере текста «babb» все действия, которые делал Никита. Сначала он выписал все подпалиндромы:

Далее Никита посчитал количество различных пар подпалиндромов, которые пересекаются. Таких пар оказалось шесть:

Так как это всё изнурительно тяжело делать вручную, Никита попросил вас помочь ему и разработать программу, которая по заданному тексту будет определять количество различных пар пересекающихся подпалиндромов. Две пары подпалиндромов называются различными, если есть подпалиндром, который входит в одну из них и не входит в другую.