N = int(input())
ans = (N << 1) % 1004535809
while N:
    ans -= N
    ans %= 1004535809
    N >>= 1
print(ans)