n = int(input()) binary = bin(n)[2:] prefix_sum = [0] * (len(binary) + 1) for i in range(len(binary)): prefix_sum[i + 1] = prefix_sum[i] + (binary[i] == '1') max_count = 0 for i in range(len(binary)): current = prefix_sum[-1] - prefix_sum[i] if current > max_count: max_count = current print(max_count % 1004535809)