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.foldl1' (\acc x -> (acc + x) `mod` 1000003) $ VU.map (\y -> powModInt x y 1000003) an