Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.

В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.

Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.

Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.

Требуется написать программу, которая по заданному процессу сборки определит количество экономически целесообразных способов использования робота.

Рассмотрим строку \(s\), состоящую из строчных букв латинского алфавита. Примером такой строки является, например, строка «abba».

Подстрокой строки \(s\) называется строка, составленная из одного или нескольких подряд идущих символов строки \(s\). Обозначим как \(W(s)\) множество, состоящее из всех возможных подстрок строки \(s\). При этом каждая подстрока входит в это множество не более одного раза, даже если она встречается в строке \(s\) несколько раз.

Например, \(W\)(«abba») = {«a», «b», «ab», «ba», «bb», «abb», «bba», «abba»}.

Подпоследовательностью строки \(s\) называется строка, которую можно получить из \(s\) удалением произвольного числа символов. Обозначим как \(Y\)(\(s\)) множество, состоящее из всех возможных подпоследовательностей строки \(s\). Аналогично \(W\)(\(s\)), каждая подпоследовательность строки \(s\) включается в \(Y\)(\(s\)) ровно один раз, даже если она может быть получена несколькими способами удаления символов из строки \(s\). Поскольку любая подстрока строки \(s\) является также ее подпоследовательностью, то множество \(Y\)(\(s\)) включает в себя \(W\)(\(s\)), но может содержать также и другие строки.

Например, \(Y\)(«abba») = \(W\)(«abba») ∪ {«aa», «aba»}. Знак ∪ обозначает объединение множеств.

Будем называть строку \(s\) странной, если для нее \(W\)(\(s\)) = \(Y\)(\(s\)). Так, строка «abba» не является странной, а, например, строка «abb» является, так как для нее \(W\)(«abb») = \(Y\)(«abb») = {«a», «b», «ab», «bb», «abb»}.

Будем называть странностью строки число ее различных странных подстрок. При вычислении странности подстрока считается один раз, даже если она встречается в строке \(s\) в качестве подстроки несколько раз. Так, для строки «abba» ее странность равна 7, любая ее подстрока, кроме всей строки, является странной.

Требуется написать программу, которая по заданной строке \(s\) определяет ее странность.