N = int(input())
mod = 1004535809
sm = 0
la = N << 1
while N > 0:
	sm += N
	N >>= 1
print(((la % mod + mod) - (sm % mod + mod)) % mod)