sums of powers

searchDfs :: (Eq node) =>
             (node -> [node]) -> -- generates successor nodes
             (node -> Bool) -> -- is goal
             node -> -- first node
             [node]
searchDfs succ goal x = search' ([x])
  where
    search' s
      | null s = []
      | goal (head s) = head s : search' (tail s)
      | otherwise = let x = head s
                    in search' (succ x ++ tail s)

type Degree = Int
type CurrentSum = Int
type CurrentNumber = Int
type Node = (CurrentSum,CurrentNumber,Degree,Goal)
type Goal = Int

succN :: Node -> [Node]
succN (sum,i,d, goal)  = [( sum+i'^d, i', d, goal) | i' <- [(i+1)..goal], sum+i'^d <= goal ]

goal :: Node -> Bool
goal (sum,_,_,m) = sum == m


countSols :: Degree -> Goal -> Int
countSols d m = foldr (+) 0 $ map (\(sum,i) -> length (searchDfs succN goal (sum,i,d,m))) startingNumbers
  where startingNumbers = [ (i^d,i) | i <- [1..m], i^d <= m]

main = do
  m <- readLn
  d <- readLn
  let c = countSols d m
  print c