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