n = gets.to_i
bc = 0
while n > 0 do
	bc = bc + (n & 1)
	n = n >> 1
end
print bc % 1004535809