-- yukicoder My Practice
-- author: Leonardone @ NEETSDKASU

main = print . solve . read =<< getLine

solve n = ans `mod` 1004535809  where
    f 0 a = a
    f x a = f (x `div` 2) ((a - x) `mod` 1004535809)
    ans = f (n `div` 2) n