Путешествия гномов
Как известно, гномы жили в лесу и путешествовали редко, передвигаясь в основном пешком. Однако они гораздо раньше людей построили своё метро и на далекие расстояния перемещались только используя его.
Путешествия занимали много времени, да и билет в метро стоил довольно больших денег. Однако они договорились, что все гномы, которым выпадет "счастливый" билет, получит его бесплатно. Счастливым в понимании гномов считался тот билет, в котором в p-ичной системе счисления сумма цифр первых k разрядов равнялась сумме цифр последних k разрядов. Известно, что номера билетов в метро у гномов всегда состоят из 2k разрядов.
А сколько гномов сможет в этом случае проехать в метро бесплатно? Учтите, что гномы очень справедливы, и если у кого-то из них уже была бесплатная поездка, он всегда уступал следующие счастливые билеты своим товарищам.
Входные данные
В единственной строке задано через пробел значения p и k.
Выходные данные
Искомое количество гномов, вычисленное по модулю 18446744073709551616.
Ограничения
Гномы по секрету сообщили, что проездом в Бухарест через Львов они узнали о счастливой львовской цифре 4, и поэтому система счисления и номера билетов у них теперь такие, что соответствуют условию: k(p-1) + 1 <= 4444.