Задача Z. Его прощальный брутфорс ≡

Условие

— Чтобы открыть такой замок, требуется знать определенное слово и определенное число. — Фон Борк поднялся и показал на двойной диск вокруг замочной скважины.

— Здорово, здорово!

— Не так-то просто, как вы думали. Я заказал его четыре года назад, и, знаете, какие я выбрал слово и число?

— Понятия не имею.

— Так вот, слушайте: слово — «август», а число — 1914, поняли?

Лицо американца выразило восхищение.

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

— Из местных тупиц-полицейских до такого ни додумается никто... Шерлок Холмс бы, пожалуй, смог, но о нём уже несколько лет ни слуху, ни духу. Так кого мне бояться?

Не говоря ни слова, американец передал пакет. Фон Борк развязал бечевку, развернул два слоя оберточной бумаги. Несколько мгновений он не сводил изумленного взгляда с небольшой книжки в синем переплете, на котором золотыми буквами было вытиснено «Практическое руководство по разведению пчел». Но долго рассматривать эту неуместную надпись ему не пришлось: руки крепкие, словно железные тиски, охватили сзади его шею и прижали к его лицу пропитанную хлороформом губку.

По данному коду определите, каким по счету он будет проверен при полном переборе. Коды проверяются в лексикографическом порядке.

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и b  — длины строковой и числовой частей кода сейфа. Во второй строке приведен сам код, состоящий из a строчных английских букв в начале и b десятичных цифр в конце.

Формат выходных данных

Выведите одно натуральное число  — каким по счету будет проверен данный код. Гарантируется, что ответ не превысит 10¹⁸.

Ограничения

1 ≤ a, b ≤ 10

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при a = 1 и b = 1, получат не менее 20 баллов.

Решения, верно работающие при a = 1, получат не менее 20 баллов.

Пояснение к примерам

В первом примере приведенный код является лексикографически наименьшим из всех возможных, его проверят первым.

Во втором примере сначала переберут 10 кодов, начинающихся на букву "a" (от a0 до a9), потом пять кодов, начинающихся на "b" (от b0 до b4).

Примеры тестов

2 3
aa000

1

1 1
b4

15

2 2
bb22

2723

6 4
august1914

92589831915