def divide_by_two(n_str):
    if n_str == '0':
        return '0'
    carry = 0
    result = []
    for c in n_str:
        current = carry * 10 + int(c)
        quotient = current // 2
        remainder = current % 2
        carry = remainder
        result.append(str(quotient))
    # Remove leading zeros
    while len(result) > 1 and result[0] == '0':
        result.pop(0)
    return ''.join(result)

def decimal_to_binary(n_str):
    if n_str == '0':
        return '0'
    binary = ''
    while n_str != '0':
        mod = int(n_str[-1]) % 2
        binary = str(mod) + binary
        n_str = divide_by_two(n_str)
    return binary

def count_set_bits(n_str):
    binary_str = decimal_to_binary(n_str)
    return binary_str.count('1')

def main():
    MOD = 1004535809
    N = input().strip()
    count = count_set_bits(N)
    print(count % MOD)

if __name__ == "__main__":
    main()