На следующий день после дискотеки Гриша решил устроить детям «взрыв мозга». Он взял много карточек и написал на каждой из них одну латинскую букву в нижнем регистре. А после этого придумал свою строку и задал детям задание: составить как можно больше подстрок своей строки, используя карточки. Гришина строка состоит только из букв латинского алфавита в нижнем регистре. Вам нужно определить сколько её подстрок можно составить, используя только данные карточки.

Запишем буквы, написанные на карточках, подряд друг за другом. Тогда если Гришина строка — это «aaab», а карточки — это «aba», то можно составить три подстроки «a», подстроку «b», две подстроки «aa» и подстроки «ab» и «aab». А подстроки «aaa» и «aaab» нельзя, так как есть всего две карточки с буквой «a».