Задача E. Система счисления остатков ≡

Условие

Никита и Женя во время уроков часто обмениваются записками с сообщениями. Естественно, они не заинтересованы в том, чтобы их сообщения могли прочитать другие ученики, поэтому ребята договорились шифровать все слова.

Очень долго ребята не могли договориться, как шифровать числа. Сначала они писали число задом наперед, потом в двоичной системе счисления, потом азбукой Морзе... Но проблема в том, что класс, где учатся ребята — с математическим уклоном, а все вышеперечисленные кодировки слишком просты. Наконец, Женя предложил такой способ.

Будем кодировать число при помощи остатков от его деления на первые 11 простых чисел (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Например, число 10 при делении на 2 даст в остатке 0 — записываем эту цифру первой. При делении на 3 число 10 даст в остатке 1 — записываем эту цифру второй. Если остаток получается двузначным (это может произойти при делении на простые числа от 11 до 31), то записываем его как цифру в 36-ой системе счисления (число 10 там запишется как A, 11 — как B, и так далее). Полученная строка из одиннадцати остатков и будет представлением исходного числа. Например, число 10 запишется как 0103AAAAAAA.

Ребята быстро убедились, что все натуральные числа от 1 до 200560490130 кодируются различным представлением. С самим кодированием проблем тоже не возникло — найти 11 остатков от деления ребятам не сложно. А вот обратный процесс (по данному представлению восстановить исходное число) вызвал у ребят затруднение. Помогите им!

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

Единственная строка входного файла содержит строку из 11 символов. Гарантируется, что все символы либо десятичные цифры, либо заглавные английские буквы.

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

Выведите одно натуральное число n — исходное закодированное число. Гарантируется, что оно не превышало 2 × 10¹¹.

Ограничения

1 ≤ n ≤ 2 × 10¹¹

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

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

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

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

0103AAAAAAA

10