N = int(input())
ans = (N << 1) % 1004535809
temp = N % 1004535809
while N:
    ans -= temp
    if N & 1:
        temp -= 1
    temp *= 1004535810 // 2
    ans %= 1004535809
    N >>= 1
print(ans)