class PowerSum
{
    // https://www.hackerrank.com/challenges/the-power-sum/problem
    // Find the number of ways that a given integer, x, can be expressed 
    // as the sum of the nth powers of unique, natural numbers.

    public PowerSum()
    {
        int x = Convert.ToInt32(Console.ReadLine());
        int n = Convert.ToInt32(Console.ReadLine());
        int result = Solve(x, n);
        Console.WriteLine(result);
        Console.ReadLine();
    }

    private int Solve(int value, int n, int a = 1)
    {
        int p = (int)Math.Pow(a, n);
        int remainingValue = value - p;

        if (remainingValue == 0)
            return 1;
        else if (p > value)
            return 0;

        return Solve(value, n, a + 1) + Solve(remainingValue, n, a + 1);
    }
}