A и B готовятся к олимпиадам про программированию.

После нескольких лет занятия спортивным программированием и решения множества задач, требующих подсчета различных абстрактных объектов, у A и B тоже сложились весьма необычные вкусы.

A увлечен строчными буквами латинского алфавита. Он присвоил каждой из них число, обозначающее насколько сильно она ему нравится (буквам, которые он недолюбливает, он присвоил отрицательное число).

B увлечен подстроками. Особенно его интересуют те из них, которые начинаются и заканчиваются на одну и ту же букву (разумеется, в таком случае их длина должна быть больше единицы).

У A и B также есть строка s. Теперь они пытаются выяснить, сколько подстрок t в s интересны для B (то есть t начинается и заканчивается на одну и ту же букву и имеет длину больше единицы) и при этом сумма значений всех букв (присвоенных A) в t, кроме первой и последней, равна нулю.

Разумеется, A и B быстро нашли количество интересующих их подстрок t. А сможете ли это сделать вы?