Теорема Ферма
...всё уже сочинено в далёкие средние века — и современными авторами только воруется. А средневековые авторы, в свою очередь, покрали эти мысли у античных, и если что-то новое у них мелькнуло — это, значит, из источников не сохранившихся и до нас не дошедших.
И. Губерман
Наверное нет ни одного человека в мире, который бы ничего не слышал о великой теореме Ферма. Она имеет уникальную историю, какую не имеет пожалуй ни одна теорема в мире, над ней бились лучшие умы планеты на протяжении 350 лет, пока она не была доказана американским математиком Эндрю Уайлсом. Формулировка теоремы чрезвычайно проста: для любого натурального числа k > 2 уравнение
x^k + y^k = z^k
не имеет натуральных решений a, b и c. Если быть точным, Ферма написал на полях книги Диофанта “Арифметика”: "Нельзя разложить куб на два куба, ни квадрато-квадрат (т. е. четвертую степень числа) на два квадрато-квадрата, ни вообще никакую степень выше квадрата и до бесконечности нельзя разложить на две степени с тем же показателем. Я открыл этому поистине чудесное доказательство, но эти поля для него слишком узки". В этой задаче Вам, конечно, не придется доказывать эту теорему, необходимо лишь по заданному натуральному числу n определить, сколькими способами оно представимо в виде суммы двух степеней натуральных чисел с показателем k. Иначе говоря, сколько существует неупорядоченных пар натуральных чисел (x, y), которые удовлетворяют уравнению:
x^k + y^k = n
Входные данные
Во входном файле содержится пара чисел n, k (1 ≤ n ≤ 10^18, 1 ≤ k ≤ 100).
Выходные данные
Выведите единственное число – количество решений уравнения.