MOD = 1004535809

def decimal_to_binary(decimal_str):
    if decimal_str == '0':
        return '0'
    decimal = list(map(int, decimal_str))
    binary_digits = []
    while decimal:
        remainder = 0
        new_decimal = []
        for digit in decimal:
            current = remainder * 10 + digit
            new_digit = current // 2
            rem = current % 2
            new_decimal.append(new_digit)
            remainder = rem
        binary_digits.append(str(remainder))
        # Remove leading zeros
        while new_decimal and new_decimal[0] == 0:
            new_decimal.pop(0)
        decimal = new_decimal
    return ''.join(reversed(binary_digits))

n_str = input().strip()
binary_str = decimal_to_binary(n_str)

cum = [0] * (len(binary_str) + 1)
for i in range(len(binary_str)):
    cum[i+1] = cum[i] + (binary_str[i] == '1')

max_count = max(cum)
print(max_count % MOD)