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

Подорожі гномів

Подорожі гномів

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB

Як відомо, гноми жили у лісі і подорожували рідко, пересуваючись в основному пішки. Проте вони набагато раніше людей побудували своє метро і на далекі відстані переміщувались лише використовуючи його.

Подорожі займали багато часу, да й квиток в метро коштував досить дорого. Проте вони домовились, що всі гноми, яким попаде "щастливий" квиток, отримають цого безкоштовно. Щасливим у розумінні гномів вважався той квиток, у якому у p-й системі числення сума цифр перших k розрядів дорівнювала сумі цифр останніх k розрядів. Відомо, що номери квитків в метро у гномів завжди містять 2k разрядів.

А скільки ж гномів зможе у цьому випадку проїхати у метро безкоштовно? Врахуйте, що гноми дуже справедливі, і якщо у когось з них вже була безкоштовна поїздка, він завжди віддавав наступні щасливі квитки своїм товаришам.

Вхідні дані

У єдиному рядку задано через пропуск значення p та k.

Вихідні дані

Шукана кількість гномів, обчислена за модулем 18446744073709551616.

Обмеження

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

Приклад

Вхідні дані #1
2 2
Вихідні дані #1
6
Автор Анатолій Присяжнюк