pow _ 0 = 1
pow x i
    | even i = pow (x * x) (i `div` 2)
    | otherwise = (pow (x * x) (i `div` 2) * x) `mod` 1000003

main = do
    [x, n] <- map read . words <$> getLine
    a <- map read . words <$> getLine
    print . (`mod` 1000003) . sum $ map (pow x) a