...everything is composed in the distant Middle Ages - and modern authors only voruetsya. A medieval writers, in turn, these thoughts have pokrali antique, and if they have something new flashed - this means that sources are not preserved and not come down to us.
J. Huberman
Probably no one person in the world who would not have heard of Fermat's Last Theorem. It has a unique history, which has perhaps not a theorem in the world, fought over it the world's best minds for 350 years until it was proved by Andrew Wiles American mathematician. Statement of the theorem is quite simple: for every integer k > 2, the equation
x^k + y^k = z^k
has no positive solutions a, b and c. To be precise, Fermat wrote in the margins of the book of Diophantus 'Arithmetic': "You can not decompose a cube into two cubes, or square-square (ie, the fourth power of the number) of two square-square, nor do any degree above the square and up to infinity can not be decomposed into two levels with the same exponent. I discovered this a truly wonderful proof, but these fields are too narrow for him." In this task, you certainly do not have to prove this theorem, it is only necessary for a given natural number n define the number of ways it can be represented as the sum of two powers of natural numbers with exponent k. In other words, as there are unordered pairs of integers (x, y), which satisfy the equation:
x^k + y^k = n
The input file contains a pair of numbers n, k (1 ≤ n ≤ 10^18, 1 ≤ k ≤ 100).
Bring a single number - the number of solutions.