#!ruby -na
eval'a=1,i=1
p 2**%s.times{a<<i+=i-=a[~%s]||0}-i'%$F