import Control.Monad
import Control.Applicative

m :: Integral a => a
m = 1000003

solve :: Integral a => a -> [a] -> a
solve _ [] = 0
solve x xs = x ^ (head xs) `mod` m + solve x (tail xs)

main = do
    [x, n]  <- map read . words <$> getLine
    as <- map read . words <$> getLine
    putStrLn $ show $ solve x as `mod` m