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

solve :: Int -> Int -> [Int] -> Int
solve x n as =
    sum (map solve' as) `mod` l
        where
            l = 10 ^ 6 + 3
            solve' :: Int -> Int
            solve' 0 = 1
            solve' a
              | odd a = (h * x) `mod` l
              | otherwise = h `mod` l
              where h = solve' (a `div` 2) ^ 2