Шесть кристаллов рождественского сейфа
В канун Рождества Рон Уизли решил подготовить для Гермионы Грейнджер особенный сюрприз и заранее заказал у Фреда и Джорджа редкий магический артефакт из их лавки. Чтобы Гермиона и никто из домашних не нашли подарок раньше времени, близнецы положили коробку в свой зачарованный сейф в «Норе» с шестью арифмантическими кристаллами и шепнули Рону на ухо секретное натуральное число — код сейфа.
Однако накануне праздника во время весёлой игры в снежки во дворе «Норы» в Рона угодил заколдованный снежок близнецов с лёгким эффектом забывчивости. Когда наступило рождественское утро и Рон подбежал к сейфу, чтобы забрать подарок для Гермионы, оказалось, что точный числовой код вылетело у него из головы! Рон смог вспомнить только то, сколько цифр было в десятичной записи этого числа, какая цифра стояла на самом первом месте и каким должен быть магический код-знак.
Зато правило работы шести арифмантических кристаллов, которое Фред и Джордж нацарапали прямо на крышке сейфа, было у него перед глазами:
- Кристаллы расположены в строгом порядке слева направо и зачарованы на простые основания систем счисления в порядке убывания: 17, 13, 11, 7, 5 и 3 соответственно.
- Когда волшебник произносит вслух любое натуральное число N, каждый кристалл сначала вычисляет его факториал (N! = 1 · 2 · … · N), затем переводит результат в систему счисления со своим основанием и высвечивает внутри грани только знак — самую правую ненулевую цифру получившейся записи (для систем с основаниями больше 10 используются стандартные латинские руны-буквы:
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15, G = 16).
- Шесть знаков, прочитанных слева направо, складываются в шестизначный код-знак замка (например,
111111 или GCA642).
Сейф откроется, если названное натуральное число сформирует на кристаллах правильный код-знак. Помогите Рону достать рождественский подарок для Гермионы: найдите наибольшее натуральное число N, которое подходит под его воспоминания о длине и первой цифре кода сейфа, а также даёт нужный код-знак на кристаллах.
Формат входных данных
- В первой строке вводится количество цифр K в десятичной записи числа N и его первая цифра D (1 ≤ K ≤ 6, 1 ≤ D ≤ 9).
- Во второй строке вводится шестисимвольный код-знак, который должны показать кристаллы. Гарантируется, что хотя бы одно подходящее натуральное число N существует.
Формат выходных данных
- Выведите одно число — наибольшее натуральное N, удовлетворяющее всем условиям.
Примеры
Пример 1
| Входные данные |
Выходные данные |
1 2
222222
|
2
|
Пояснение: Рон помнит, что код состоит из 1 цифры и начинается на 2 — единственным кандидатом является N = 2. Вычислим 2! = 2. Переведём число 2 во все шесть систем счисления:
- Основание 17: 210 =
217 → самая правая ненулевая цифра 2.
- Основание 13: 210 =
213 → самая правая ненулевая цифра 2.
- Основание 11: 210 =
211 → самая правая ненулевая цифра 2.
- Основание 7: 210 =
27 → самая правая ненулевая цифра 2.
- Основание 5: 210 =
25 → самая правая ненулевая цифра 2.
- Основание 3: 210 =
23 → самая правая ненулевая цифра 2.
Собрав знаки слева направо, получаем код-знак 222222.
Пример 2
| Входные данные |
Выходные данные |
1 4
7B2342
|
4
|
Пояснение: Для N = 4 получаем 4! = 24. Переведём число 24 в системы счисления каждого из шести кристаллов (в порядке 17, 13, 11, 7, 5, 3) и найдём самую правую ненулевую цифру:
- Основание 17: 2410 =
1717 (так как 1 · 17 + 7 = 24) → знак 7.
- Основание 13: 2410 =
1B13 (так как 1 · 13 + 11 = 24, цифра 11 обозначается буквой B) → знак B.
- Основание 11: 2410 =
2211 → знак 2.
- Основание 7: 2410 =
337 → знак 3.
- Основание 5: 2410 =
445 → знак 4.
- Основание 3: 2410 =
2203 → знак 2.
Собрав знаки слева направо, получаем код-знак 7B2342.
Пример 3
| Входные данные |
Выходные данные |
2 1
GA9642
|
18
|
Пояснение: Рон проверяет двузначные числа, начинающиеся с единицы (из диапазона от 10 до 19), двигаясь по убыванию — от 19 вниз к 10:
- Для N = 19 получается код-знак
F86212, что не подходит.
- Следующим проверяется N = 18. Вычислим 18! = 6 402 373 705 728 000 и переведём это число в системы счисления всех шести кристаллов:
- Основание 17: 6 402 373 705 728 00010 =
AGDD765B933G017 → знак G (последняя цифра перед нулём).
- Основание 13: 6 402 373 705 728 00010 =
181A58332C7C2A013 → знак A (последняя цифра перед нулём).
- Основание 11: 6 402 373 705 728 00010 =
1594AA249338859011 → знак 9 (последняя цифра перед нулём).
- Основание 7: 6 402 373 705 728 00010 =
36343631436024066007 → знак 6 (последняя цифра перед двумя нулями).
- Основание 5: 6 402 373 705 728 00010 =
232031324423221312440005 → знак 4 (последняя цифра перед тремя нулями).
- Основание 3: 6 402 373 705 728 00010 =
10110021202202211211220222000000003 → знак 2 (последняя цифра перед восемью нулями).
Собрав знаки слева направо, получаем нужный код-знак GA9642. Так как мы идём по убыванию, N = 18 является наибольшим подходящим числом.