n=int(input())
a=0
acc = n
while acc > 0:
    a += acc
    acc >>= 1
print((2*n - a) % 1004535809)