MOD = 1004535809

n = input().strip()

count = 0
s = n
while s != '0':
    rem = 0
    new_s = []
    for c in s:
        num = rem * 10 + int(c)
        new_rem = num % 2
        q = num // 2
        new_s.append(str(q))
        rem = new_rem
    count = (count + rem) % MOD
    # Remove leading zeros
    s = ''.join(new_s).lstrip('0') or '0'

print(count % MOD)