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];
}
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