Магія

Зараз триває урок англійської мови в 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$.