На уроке физкультуры математик Виктор выполнял подъём с переворотом. Придя домой, он задумался, могут ли числа выполнять то же упражнение? Подъёмом для чисел Виктор считает операцию замены каждой цифры в числе на следующую по значению (9 заменяется на 0), а переворотом - запись числа справа налево (ведущие нули отбрасываются). Подъём выполняется до переворота. Виктор записывает число ему определить, что получится после применения подъёма с переворотом к этому числу. Поскольку результат может оказаться очень большим, Виктора интересуют только его последние M цифр. Формат ввода
В первой строке вводится натуральное число N, длина которого не превышает 100000 цифр. Во второй строке вводится натуральное число M ≤ 100000.
Формат вывода
Программа должна вывести результат подъёма с переворотом, или последние его M цифр, если в результате более M цифр.
Пример 1
Ввод Вывод
123
3
432
Пример 2
Ввод Вывод
1799
3
82
Начинаем с единицы и смотрим, если дальше идет 0, то просто умножаем результат на 2, но т.к. у нас пока только 1, то умножаем 1 на 2 и получаем 2. Дальше идет 1, теперь нам надо результат умножить на 2 и прибавить 1. Т.е. каждый раз когда ты видишь 0, то просто умножь на 2, а если видишь 1, то после умножения прибавь один. Так у нас получается 1389
Теперь перевод в 16 систему
полученое число нужно делить на 16
1389/16=86, остаток = 13, он нам и нужен. На 16 языке, 10=А, 11=B 12=C, 13=D, 14=E, 15=F. 16 там нету, ибо система ведет отчет с нуля.
Запоминаем D. 86/16=5, остаток 6. Теперь ставим наши цифры/буквы в обратном порядке(так надо делать всегда), и получаем 56D
ОТВЕТ: 56D