import           Control.Arrow
import qualified Data.ByteString.Char8     as BSC8
import qualified Data.Vector.Unboxed       as VU
import qualified GHC.Integer.GMP.Internals as GMP

fi :: Int -> Integer
fi = fromIntegral
{-# INLINE fi #-}

fI :: Integer -> Int
fI = fromInteger
{-# INLINE fI #-}

powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fI $ GMP.powModInteger (fi a) (fi n) (fi mo)

type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (second BSC8.tail) . BSC8.readInt
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine

main :: IO ()
main = do
  [x, m] <- map (read :: String -> Int) . words <$> getLine
  an <- parseM m
  print $ VU.sum $ VU.map (\y -> powModInt x y 1000003) an