import java.io.*;
import java.util.*;
 
class Solution {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int X = in.nextInt(), N = in.nextInt();
        int[] count = new int[X+1];
        count[0] = 1;
        ArrayList<Integer> list = new ArrayList<>();
        int cur = 1, p = 1;
        while((p = pow(cur++, N))<= X)list.add(p);
        for(int i:list)for(int j = X-i; j>=0; j--)count[j+i] += count[j];
 
        System.out.println(count[X]);
    }
 
    static int pow(int i, int p){
        int out = 1;
        while(p>0){
            if(p%2==1)out *= i;
            i = i*i;
            p>>=1;
            if(out>1000)return 1000000;
        }
        return out;
    }
}

aW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgU29sdXRpb24gewoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTY2FubmVyIGluID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKICAgICAgICBpbnQgWCA9IGluLm5leHRJbnQoKSwgTiA9IGluLm5leHRJbnQoKTsKICAgICAgICBpbnRbXSBjb3VudCA9IG5ldyBpbnRbWCsxXTsKICAgICAgICBjb3VudFswXSA9IDE7CiAgICAgICAgQXJyYXlMaXN0PEludGVnZXI+IGxpc3QgPSBuZXcgQXJyYXlMaXN0PD4oKTsKICAgICAgICBpbnQgY3VyID0gMSwgcCA9IDE7CiAgICAgICAgd2hpbGUoKHAgPSBwb3coY3VyKyssIE4pKTw9IFgpbGlzdC5hZGQocCk7CiAgICAgICAgZm9yKGludCBpOmxpc3QpZm9yKGludCBqID0gWC1pOyBqPj0wOyBqLS0pY291bnRbaitpXSArPSBjb3VudFtqXTsKICAgICAgICAKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oY291bnRbWF0pOwogICAgfQogICAgCiAgICBzdGF0aWMgaW50IHBvdyhpbnQgaSwgaW50IHApewogICAgICAgIGludCBvdXQgPSAxOwogICAgICAgIHdoaWxlKHA+MCl7CiAgICAgICAgICAgIGlmKHAlMj09MSlvdXQgKj0gaTsKICAgICAgICAgICAgaSA9IGkqaTsKICAgICAgICAgICAgcD4+PTE7CiAgICAgICAgICAgIGlmKG91dD4xMDAwKXJldHVybiAxMDAwMDAwOwogICAgICAgIH0KICAgICAgICByZXR1cm4gb3V0OwogICAgfQp9

MTAwIDI=

100 2