require 'matrix'

class Matrix
  def % d; map{|e| e % d} end
end

m = Matrix[[1, 3], [1, 1]]
l = Matrix.I(2)

n = gets.chomp.to_i
_n = n

while _n > 0 do
  l = l * m % 1000 if (_n & 1) == 1
  _n >>= 1
  m = m * m % 1000
end

print (l[0, 0] * 2 % 1000 + (n % 2 == 0 ? 999 : 0)) % 1000
puts