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