Statement is not available in English language
A. Могучие Промежуточники
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Могучие Промежуточники выписали все степени числа $$$k$$$ в $$$k$$$-ичной системе счисления подряд без пробелов. Сначала первую степень, затем вторую степень, третью степень и так далее до бесконечности. Дабы быть уверенными в верности своего могучего разума, побеждающего вселенских врагов этого мира, они решили проверить верность записи $$$n$$$-й цифры данного числа, узнать которую они вас и просят.

Входные данные

Вам даны два целых числа, порождённых разумом Могучих Промежуточников: $$$k$$$ и $$$n$$$ ($$$2\le k \le 36$$$, $$$1\le n \le 10^{18}$$$) — основание системы счисления и номер позиции.

Выходные данные

Выведите $$$n$$$-ю цифру получившегося числа. В системе счисления по основанию $$$k$$$ в качестве цифр используются первые $$$k$$$ символов строки 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ в заданном порядке.

Система оценки

В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.

ПодзадачаБаллыДополнительныеНеобходимыеСистема
ограниченияподзадачиоценки
$$$0$$$$$$0$$$Тесты из условия——
$$$1$$$$$$41$$$$$$N \le 10^6$$$$$$0$$$полная
$$$2$$$$$$32$$$$$$N \le 10^{12}$$$$$$0,\ 1$$$полная
$$$3$$$$$$27$$$—$$$0,\ 1,\ 2$$$полная

Пример
Входные данные
2 1
Выходные данные
1
Примечание

Следует обратить внимание, что число $$$n$$$ в этой задаче не помещается в стандартный 32-битный тип данных. Необходимо использовать 64-битный тип данных (long long в C++, int64 в Паскале, long в Java).