#!ruby -n
a=m=10**9;b=1
('%b'%$_).bytes{|c|a,b=a*a+b*b,b*(2*a+b)%m
c<49&&a=b-b=a%m}
p b