loop{a=m=10**9
('%b'.%gets*b=1).bytes{|c|a,b=a*a+b*b,b*(2*a+b)%m
c<49&&a=b-b=a%m}
p b}