На Васином любимом сайте обнаружилась уязвимость: недоброжелатель может узнать, сколько раз встречался каждый символ в пароле. И такая напасть, что сайт позволяет использовать в качестве символов пароля только латинские строчные и заглавные буквы, а также цифры. И никаких спецсимволов!
На сайте отсутствует защита от ботов: ни капч, ни двухфакторной аутентификации. Брутфорсь в удовольствие.
Вася придумал новый пароль, и ему интересно, насколько он надёжен при учёте этой уязвимости. Но сам он только новости про уязвимости читает, а код написать не может – просит Вас.
Нужно найти, с какой попытки зайдёт в его аккаунт взломщик, узнавший набор символов, которые встречаются в пароле, если будет перебирать все подходящие пароли в лексикографическом порядке.

Формат входных данных
В первой строке входного файла содержится натуральное число N – длина пароля (1 ⩽ N ⩽ 100).
Во вторую строку записана последовательность символов длины N, состоящая только из цифр и из букв латинского алфавита, как строчных, так и заглавных.

Формат выходных данных
В выходной файл необходимо вывести одно натуральное число – номер попытки, с которой будет введён правильный пароль, если перебирать все пароли в лексикографическом порядке, а попытки считать с единицы.
Так как число может получиться очень большим, то требуется вывести его по модулю 10^9 + 7.

Примеры

input.txt
5
bOjXg

output.txt
53

input.txt
10
fg6Fg10000

output.txt
60030

input.txt
5
JJJJJ

output.txt
1

Примечание
Лексикографический порядок – это отношение любых строк такое, что строка α предшествует строке B, если:
1. Любые первые m символов совпадают, а (m+1)-й символ строки α меньше (m+1)-го символа строки B. При этом считается, что буквы сравниваются согласно их кодам в ASCII, то есть цифры меньше заглавных латинских букв, а заглавные латинские буквы меньше строчных латинских букв.
Пример: GREW < GROW

2. Строка a является началом строки B
Пример: GROW < GROWN