import Control.Applicative ((<$>))

mod'' :: Integral a => a -> a
mod'' = flip mod 1000003

modPow :: Integral a => a -> a -> a
modPow x n
    | n == 0 = 1
    | even n = mod'' $ modPow (x' ^ 2) (n `div` 2)
    | odd n  = mod'' $ x' * modPow x' (n - 1)
    where
        x' = mod'' x

modSum :: Integral a => [a] -> a
modSum (x : []) = mod'' $ x
modSum (x : xs) = mod'' $ x + modSum xs

solve :: Integral a => a -> [a] -> a
solve x as = modSum $ map (x `modPow`) as

main = do
    [x, n] <- map read . words <$> getLine
    as     <- map read . words <$> getLine
    print $ solve x as