import java.util.Scanner;

public class PowerSum {


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        int power = sc.nextInt();
        rec(x,power,0,1);
        System.out.println(c);
    }

    static int c = 0;
    static void rec(int x, int power, double d, int j) {
        if(x==d) {
            c++;
            return;
        }

        for(int i = j; d+Math.pow(i, power)<=x; i++) {
            rec(x,power,d+Math.pow(i, power),i+1);
        }

    }
}