H. Разделение на части
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.

Он хочет разделить свою строку на части, причем должны выполняться следующие условия:

  • в каждой части должно быть ровно две различные буквы, причем все одинаковые буквы в каждой части должны идти подряд;
  • каждая часть – это некоторая последовательность подряд идущих букв строки $$$s$$$;
  • каждая буква строки $$$s$$$ должна оказаться ровно в одной части.

Перед вами стоит задача определить количество способов разделить строку $$$s$$$ на части таким образом, чтобы выполнялись все описанные условия. Так как ответ может быть достаточно большим, выведите его по модулю $$$1\,000\,000\,007$$$.

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

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество букв в строке Монокарпа.

Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.

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

Выведите количество способов разделить строку $$$s$$$ на части таким образом, чтобы выполнялись все описанные условия. Так как ответ может быть достаточно большим, выведите его по модулю $$$1\,000\,000\,007$$$.

Примеры
Входные данные
6
rbbbrr
Выходные данные
2
Входные данные
6
vkosph
Выходные данные
1
Входные данные
3
abc
Выходные данные
0
Входные данные
18
aaabbbcccbbddaaaba
Выходные данные
12
Примечание

В первом примере есть два способа разделения: [rb, bbrr] и [rbb, brr].

Во втором примере есть один способ разделения: [vk, os, ph].

В третьем примере нет ни одного подходящего способа разделения.