A = B+C

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

找出给定正整数X能被唯一正整数的N次幂和表示的方法数。

也就是说,我们需要用一些数的和来表示X,这些数是一些不同的正整数的N次方。

唯一的意思是,每个正整数仅能被用一次。

例如,假设X = 13 and N = 2,我们需要找出所有唯一正整数加起来等于13的方式,唯一的方式是 2^2+3^2 = 13。

Input

一共有两行。

第一行为整数X,第二行为整数N。

(1 <= X <= 1000,2 <= N <= 10)

Output

输出一个整数,即给定整数X能被唯一正整数的N次幂和表示的方法数。

Sample Input

100 
2

Sample Output

3

Hint

例如,样例的三种方案数分别为:

100 = 6^2+8^2

100 = 10^2

100 = 1^2+3^2+4^2+5^2+7^2

Source

axuhongbo