change [] n = if n == 0 then 1 else 0
change (x:xs) n = foldl (+) 0 $ map ((change xs).(n-)) avail
    where avail = takeWhile (<=n) $ map (x*) [0..]

change' xs n = (foldl (flip $ (+).fst) 0).head.(drop n) $ [(1,0)]:changeIter [[(1,0)]]
    where changeIter hist = h:(changeIter (h:hist))
            where h = [ (foldl (+) 0 $ [m |(m,low)<-getH x,low<=x],x) |x<-xs]
                  getH x = let left=drop (x-1) hist in 
                    if left/=[] then head left else []

main = putStrLn (show $ change' [25,10,5,1] 100000000)