N = int(raw_input())
n = len(format(N,"b"))
a = 2*N
for i in xrange(n):
	a -= N
	N >>= 1
print a % 1004535809