print (lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y))))(lambda f: lambda n: n%2+f(n/2) if n>0 else 0)(input()*2)%10045358091004535809