n = int(input())
ans = 0
while n > 0:
    ans += n % 2
    n >>= 1
print(ans % 1004535809)