def main():
    MOD = 1004535809
    n_str = input().strip()
    
    # Convert N to an integer
    n = int(n_str)
    
    # Convert to binary string
    bin_str = bin(n)[2:]
    L = len(bin_str)
    
    # Compute cumulative sum of '1's from the start (most significant bit)
    cumulative = [0] * (L + 1)
    for i in range(L):
        cumulative[i+1] = cumulative[i] + (1 if bin_str[i] == '1' else 0)
    
    max_profit = 0
    for k in range(1, L + 1):
        pos = L - k
        if pos < 0:
            bit = 0
        else:
            bit = 1 if bin_str[pos] == '1' else 0
        count = cumulative[L - k]
        profit = bit + count
        if profit > max_profit:
            max_profit = profit
    
    print(max_profit % MOD)

if __name__ == "__main__":
    main()