n = int(input())
m = n
sum = 0
while m > 0:
    sum = (sum + m) % 1004535809
    m = m // 2
print((n*2 - sum) % 1004535809)