import Control.Applicative ((<$>))

modexp :: Integral a => a -> a -> a -> a
modexp b ex m
    | ex == 0   = 1
    | even ex   = flip mod m $ (\x -> x * x) $ flip mod m $ modexp b (div ex 2) m 
    | otherwise = flip mod m $ mod b m * (flip mod m $ modexp b (ex - 1) m)

calc :: Integral a => a -> [a] -> a
calc x = flip mod m . mysum . map (\k -> modexp x k m)
    where
        m = 1000003
        mysum [] = 0
        mysum (y : ys) = mod y m + mysum ys

main :: IO ()
main = do
    (x : _ : _) <- map read . words <$> getLine
    print . calc x . map read . words =<< getLine