def decimal_to_bin(s):
    if s == '0':
        return '0'
    bin_str = ''
    num = s
    while num != '0':
        quotient, rem = divide_by_two(num)
        bin_str += str(rem)
        num = quotient
    bin_str = bin_str[::-1]
    return bin_str

def divide_by_two(num_str):
    rem = 0
    quotient = []
    for c in num_str:
        digit = int(c)
        current = rem * 10 + digit
        rem = current % 2
        quotient_digit = current // 2
        quotient.append(str(quotient_digit))
    # Remove leading zeros
    while len(quotient) > 0 and quotient[0] == '0':
        quotient.pop(0)
    if not quotient:
        quotient_str = '0'
    else:
        quotient_str = ''.join(quotient)
    return quotient_str, rem

def count_set_bits(num_str):
    if num_str == '0':
        return 0
    bin_str = decimal_to_bin(num_str)
    return bin_str.count('1')

def main():
    import sys
    input = sys.stdin.read().strip()
    n = input
    if n == '0':
        print(0)
        return
    max_extra = count_set_bits(n)
    print(max_extra % 1004535809)

if __name__ == "__main__":
    main()