calc 0 = 0
calc n = n + calc (n`div`2)

main = do
	n <- return . (read::String->Integer) =<< getLine
	print $ (n * 2 - calc n) `mod` 1004535809