eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Путешествия гномов

Путешествия гномов

Лимит времени 0.5 секунд
Лимит использования памяти 64 MiB

Как известно, гномы жили в лесу и путешествовали редко, передвигаясь в основном пешком. Однако они гораздо раньше людей построили своё метро и на далекие расстояния перемещались только используя его.

Путешествия занимали много времени, да и билет в метро стоил довольно больших денег. Однако они договорились, что все гномы, которым выпадет "счастливый" билет, получит его бесплатно. Счастливым в понимании гномов считался тот билет, в котором в p-ичной системе счисления сумма цифр первых k разрядов равнялась сумме цифр последних k разрядов. Известно, что номера билетов в метро у гномов всегда состоят из 2k разрядов.

А сколько гномов сможет в этом случае проехать в метро бесплатно? Учтите, что гномы очень справедливы, и если у кого-то из них уже была бесплатная поездка, он всегда уступал следующие счастливые билеты своим товарищам.

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

В единственной строке задано через пробел значения p и k.

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

Искомое количество гномов, вычисленное по модулю 18446744073709551616.

Ограничения

Гномы по секрету сообщили, что проездом в Бухарест через Львов они узнали о счастливой львовской цифре 4, и поэтому система счисления и номера билетов у них теперь такие, что соответствуют условию: k(p-1) + 1 <= 4444.

Пример

Входные данные #1
2 2
Выходные данные #1
6