n_str = input().strip()
n = int(n_str)
binary = bin(n)[2:]  # Convert to binary and remove '0b' prefix
L = len(binary)
prefix = [0] * (L + 1)

# Compute prefix sums of 1s in the binary string
for i in range(L):
    prefix[i+1] = prefix[i] + (1 if binary[i] == '1' else 0)

max_s = 0
# Check all possible shifts (m) from 0 to L-1
for m in range(L):
    current = prefix[L] - prefix[m]
    if current > max_s:
        max_s = current

print(max_s % 1004535809)