a=[2,2]
n=10**8
(2..1200).each{|i|a<<(a[i-1]+a[i-2]<<1)%1000}
i=a[n%600+600]
p n&1<1?i-1:i