MOD = 1004535809

def main():
    import sys
    input = sys.stdin.read().strip()
    if input == '0':
        print(0)
        return
    
    # Convert decimal string to binary string
    binary = decimal_to_binary(input)
    n = len(binary)
    
    # Calculate the sum of '1's from each position to the end
    sum_ones = [0] * (n + 1)
    for i in range(n-1, -1, -1):
        sum_ones[i] = sum_ones[i+1] + (1 if binary[i] == '1' else 0)
    
    max_ones = max(sum_ones)
    print(max_ones % MOD)

def decimal_to_binary(s):
    if s == '0':
        return '0'
    s = list(s)
    binary = []
    while any(c != '0' for c in s):
        remainder = 0
        new_s = []
        for c in s:
            num = remainder * 10 + int(c)
            q = num // 2
            remainder = num % 2
            if q != 0 or new_s:
                new_s.append(str(q))
        binary.append(str(remainder))
        s = new_s if new_s else ['0']
    return ''.join(reversed(binary)) if binary else '0'

if __name__ == "__main__":
    main()