n = gets.chomp.to_i
mod = 1004535809
x = 2*(n%mod)%mod
y = 0
while n>0
  y += n%mod
  n /= 2
end
y %= mod
ans = x-y+mod+mod
ans %= mod
puts ans