myDropWhile :: (a -> Bool) -> [a] -> [a]
myDropWhile _ [] = []
myDropWhile f (x:xs)
        | f x = myDropWhile f xs
        | otherwise = x:myDropWhile f xs
        
upperLimit :: (Integral a) => a
upperLimit = round . sqrt $ 1000

powerNat :: (Integral a) => a -> a -> [a] -> [a]
powerNat a b
        | a < 1 = error "out of scope"
        | a > 1000 = error "out of scope"
        | b < 2 = error "out of scope"
        | b > 10 = error "out of scope"
        | otherwise = foldr (\x acc -> if (((x^b) + (sum . map (^b) $ acc)) <= a)
                                       then x:acc
                                       else acc) []
                                       
uniquePowerNats :: (Integral a) => a -> a -> [a] -> [[a]]
uniquePowerNats _ _ [] = []
uniquePowerNats a b xs = natNum : uniquePowerNats a b (restNum xs)
        where natNum = powerNat a b xs
              restNum = (\ys -> if ((sum . map (^b) $ natNum) == a)
                                then filter (<(last natNum)) $ myDropWhile (`elem`natNum) xs
                                else take ((length xs) - 1) xs)
                                
main = do
       a <- getLine
       b <- getLine
       let num = read a :: Int
       let pow = read b :: Int
       putStrLn $ show . 
                  length . 
                  filter (\xs -> (sum . map (^pow) $ xs) == num) .
                  uniquePowerNats num pow $ [1..upperLimit]