def main():
    N = input().strip()
    n = int(N)
    bin_str = bin(n)[2:]
    L = len(bin_str)
    
    imos = [0] * (L + 2)
    
    for i in range(L):
        if bin_str[i] == '1':
            end = i + 1
            imos[0] += 1
            if end <= L + 1:
                imos[end] -= 1
    
    max_count = 0
    current = 0
    for k in range(L + 1):
        current += imos[k]
        if current > max_count:
            max_count = current
    
    print(max_count % 1004535809)

if __name__ == "__main__":
    main()