Магия

Сейчас проходит урок английского языка в 9 классе с господином Даскаловым. Наша главная героиня Дени очень слабо говорит по-английски и считает мух в комнате. Это оказывается очень скучным занятием, поэтому она смотрит на доску, где учитель написал какой-то текст. Она игнорирует пробелы между словами, поэтому весь текст кажется ей одной большой последовательностью английских букв длины $n$. Обозначим количество различных символов в этой последовательности через $k$. Дени начинает брать разные подстроки из этой последовательности и записывает, сколько раз встречается каждый символ. Когда для всех $k$ букв эти числа одинаковы, она называет текущую подстроку магической.

Примечание. Подстрока — это часть заданной строки, которая содержит последовательно написанные символы.

Во время текущего урока английского языка она может проверить каждую подстроку последовательности. Тем временем она подсчитала, сколько подстрок являются магическими, и в итоге осталась очень довольной проделанной работой. Дени решила, что она хотела бы заниматься этим на каждом уроке английского языка. Но с каждым последующим уроком английского текст на доске, написанный господином Даскаловым, становится все длиннее и длиннее. Поэтому она просит Вашей помощи — Вы должны написать программу, которая сообщит ей количество магических подстрок в заданной последовательности из $n$ английских букв.

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

Входные данные

Первая строка содержит одно целое число $n(2\le n\le 10^5)$ — количество символов в последовательности господина Даскалова. Вторая строка состоит из $n$ английских букв. Буквы могут быть заглавными и прописными. Обратите внимание, что заглавными и прописные формы одной и той же буквы считаются разными символами ($A$ и $a$ — разные символы).

Выходные данные

Выведите количество магических подстрок в заданной строке. Поскольку это число может быть большим, выведите его остаток от деления на $10^9+7$.

Примеры

Пояснение для 1 теста. Магическими подстроками будут $abc,cba,abc$ и $abccba$. Отметим, что подстрока $ab$ не является магической так как буква $c$ не встречается в ней.

Пояснение для 2 теста. Только подстрока $abcABC$ является магической (буквы $a$ и $A$ различны потому что $a$ буква нижнего регистра, а $A$ буква верхнего регистра).

Пояснение для 3 теста. Число магических строк равно $22$ и одной из них является $SwSwwS$.