MOD = 1004535809

N = input().strip()
n = int(N)
bin_str = bin(n)[2:]

prefix = [0] * (len(bin_str) + 1)
for i in range(len(bin_str)):
    prefix[i+1] = prefix[i] + (1 if bin_str[i] == '1' else 0)

max_ones = 0
for s in range(0, len(bin_str) + 1):
    length = len(bin_str) - s
    if length <= 0:
        ones = 0
    else:
        ones = prefix[length]
    if ones > max_ones:
        max_ones = ones

print(max_ones % MOD)