N=int(input())
mod=1004535809
ans=N*2%mod
while N:
    ret=N%mod
    ans=(ans-ret+mod)%mod
    N//=2
print(ans)