M = 1004535809

def normal(n):
    ret = 0
    while n > 0:
        ret += n
        ret %= M
        n //= 2
    return ret

def with_skil(n):
    ret = 0
    c = 0
    while n > 0:
        ret = max(ret, (c + 2 * n) % MOD)
        c += n
        c %= MOD
        n //= 2
        ret = max(ret, c)
    return ret

n = int(input())
print(with_skil(n) - normal(n))