A и B готовятся к олимпиадам про программированию.
После нескольких лет занятия спортивным программированием и решения множества задач, требующих подсчета различных абстрактных объектов, у A и B тоже сложились весьма необычные вкусы.
A увлечен строчными буквами латинского алфавита. Он присвоил каждой из них число, обозначающее насколько сильно она ему нравится (буквам, которые он недолюбливает, он присвоил отрицательное число).
B увлечен подстроками. Особенно его интересуют те из них, которые начинаются и заканчиваются на одну и ту же букву (разумеется, в таком случае их длина должна быть больше единицы).
У A и B также есть строка s. Теперь они пытаются выяснить, сколько подстрок t в s интересны для B (то есть t начинается и заканчивается на одну и ту же букву и имеет длину больше единицы) и при этом сумма значений всех букв (присвоенных A) в t, кроме первой и последней, равна нулю.
Разумеется, A и B быстро нашли количество интересующих их подстрок t. А сможете ли это сделать вы?
Примечание
В первом тестовом примере нам подходят подстроки abca и bcab.
Во втором тестовом примере нам подходит подстрока aa, которая встречается 2 раза.