MOD = 1004535809

def main():
    s = input().strip()
    count = 0
    num = list(map(int, s))
    while num:
        remainder = 0
        new_num = []
        for digit in num:
            val = remainder * 10 + digit
            new_digit = val // 2
            remainder = val % 2
            if new_num or new_digit != 0:
                new_num.append(new_digit)
        count += remainder
        num = new_num
    print(count % MOD)

if __name__ == '__main__':
    main()