За время своего изучения марсиан Петя хорошо понял, что марсиане крайне ленивые. Они любят спать и совсем не любят просыпаться.

Представьте себе марсианина имеющего ровно n глаз расположенных в ряд, и пронумерованных слева направо от 1 до n. Когда марсианин спит, он одевает на каждый свой глаз по повязке (чтобы утром марсианский свет не заставил его проснуться). С внутренней стороны каждой повязки написана одна прописная буква латинского алфавита, поэтому, когда марсианин утром просыпается и открывает все свои глаза, он видит строку s из прописных букв латинского алфавита длины n.

«Динь-дилинь!» — звонит будильник. Марсианин уже проснулся, но еще не открыл ни одного своего глаза. Он догадывается, что день сегодня будет трудным, поэтому ему хочется открыть глаза и увидеть что-нибудь хорошее. Марсианин считает, что только m слов марсианского языка красивые. Также с утра ему очень сложно открыть все глаза сразу, поэтому он открывает два не накладывающихся отрезка последовательных глаз. Более формально, марсианин выбирает четыре числа a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ n) и открывает все глаза с номерами i такими, что a ≤ i ≤ b или c ≤ i ≤ d. После того как марсианин открыл нужные ему глаза, он читает все видимые символы слева направо, получая тем самым какое-то слово.

Рассмотрим все различные слова, которые может увидеть с утра марсианин. Вам требуется узнать, сколько среди этих слов красивых.