Теорема Ферма#3247
...усe вже придумано у далекі середні віки — і сучасними авторами лише крадеться. А середньовічні автори, у свою чергу, вкрали ці думки у античних, і якщо щось нове у них промайнуло — це, значить, з джерел, які не збереглись і до нас не дійшли.
І. Губерман
Напевно немає жодної людини у світі, яка б нічого не чула про велику теорему Ферма. Вона має унікальну історію, яку не має напевно жодна теорема у світі, над нею бились кращі розуми планети протягом років, поки вона не була доведена американським математиком Ендрю Уайлсом. Формулювання теореми надзвичайно просте: для довільного натурального числа k > 2 рівняння
не має натуральних розв'язків , та . Якщо бути точним, Ферма написав на полях книги Діофанта "Арифметика": "Не можна розкласти жоден куб на два куби, ні квадратно-квадрат (тобто четверту степінь числа) на два квадратно-квадрати, ні взагалі ніякий степінь вище квадрату і до нескінченності не можна розкласти на два степені з тим же показником. Я відкрив цьому воістину прекрасне доведення, але ці поля для нього замалі". У цій задачі Вам, звичайно, не доведеться доводити цю теорему, необхідно лише за заданим натуральним числом визначити, скількома способами його можна подати у вигляді суми двох степенів натуральних чисел з показником . Інакше кажучи, скільки існує невпорядкованих пар натуральних чисел , які задовольняють рівняння:
У вхідному файлі міститься пара чисел , (1 \leq n \leq 10^{18}, 1 \leq k \leq 100).
Виведіть єдине число – кількість розв'язків рівняння.
Приклад 1