N = int(input())
P = 1004535809

ans = 2 * N % P
while N:
    ans -= N
    ans %= P
    N >>= 1
print(ans)