module Main where import System.Environment (getArgs) data Trie = !Trie :+ !Trie | End !Integer first = go (End 0) (End 1) (End 0) where go a _ _ 1 = a go a b c n = go (b :+ c) a b (n-1) (l1 :+ r1) & (l2 :+ r2) = (l1 & l2) :+ (r1 & r2) End a & End b = End (a + b) t & End _ = t _ & t = t count (l :+ r) = count l + count r count (End n) = n step (l :+ r) = h1 r :+ h_1 l where h_1 (l :+ r) = h1 l & h2 r h_1 _ = End 0 h0 (End n) = End n h0 _ = End 0 h1 (l :+ r) = (h1 l & h2 r) :+ (h0 l & h1 r) h1 _ = End 0 h2 (End 0) = End 0 h2 (End n) = End n :+ End 0 h2 (l :+ r) = End 0 :+ (h1 l & h2 r) step x = x solve w h = count (iterate step (first w) !! (h-1)) main = do [x,y] <- mapM readIO =<< getArgs print (solve x y)