def main(): MOD = 1004535809 N_str = input().strip() n = int(N_str) binary = bin(n)[2:] # Convert to binary without '0b' prefix L = len(binary) # Compute prefix sum of '1's in binary prefix_sum = [0] * (L + 1) for i in range(L): prefix_sum[i+1] = prefix_sum[i] + (binary[i] == '1') binary_rev = binary[::-1] max_extra = 0 for k in range(1, L + 1): available = L - k s = prefix_sum[available] if available >= 0 else 0 if (k - 1) < len(binary_rev): r = 1 if binary_rev[k-1] == '1' else 0 else: r = 0 current = r + s if current > max_extra: max_extra = current print(max_extra % MOD) if __name__ == "__main__": main()