{-# LANGUAGE DeriveFunctor                                          #-}
{-# LANGUAGE BangPatterns, BinaryLiterals, CPP, DerivingStrategies  #-}
{-# LANGUAGE DerivingVia, FlexibleContexts, FlexibleInstances       #-}
{-# LANGUAGE GeneralizedNewtypeDeriving, KindSignatures, LambdaCase #-}
{-# LANGUAGE MagicHash, MultiParamTypeClasses, MultiWayIf           #-}
{-# LANGUAGE NumericUnderscores, OverloadedStrings, PatternSynonyms #-}
{-# LANGUAGE RankNTypes, RecordWildCards, ScopedTypeVariables       #-}
{-# LANGUAGE StandaloneDeriving, TupleSections, TypeApplications    #-}
{-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns  #-}

{- base -}
import           Control.Applicative
import qualified Control.Arrow                 as Arrow
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Bool
import           Data.Complex
import qualified Data.Char                     as Char
import qualified Data.Foldable                 as Foldable
import           Data.Function
import qualified Data.List                     as List
import           Data.Maybe
import           Data.Monoid
import           Data.Ratio
import           Data.Ord
import           Data.Semigroup
import qualified Data.Word                     as Word
import           Foreign                       hiding (void)
import           GHC.Exts
import           Unsafe.Coerce
{- array -}
import qualified Data.Array.IO                 as ArrIO
import qualified Data.Array.MArray             as ArrMA
import qualified Data.Array.ST                 as ArrST
import qualified Data.Array.Storable           as ArrStore
import qualified Data.Array.Unboxed            as ArrU
{- bytestring -}
import qualified Data.ByteString               as BS
import qualified Data.ByteString.Builder       as BSB
import qualified Data.ByteString.Builder.Extra as BSBE
import qualified Data.ByteString.Char8         as BSC8
import qualified Data.ByteString.Lazy          as BSL
import qualified Data.ByteString.Lazy.Builder  as BSLB
import qualified Data.ByteString.Lazy.Char8    as BSLC8
import qualified Data.ByteString.Unsafe        as BSU
{- containers -}
import qualified Data.Graph                    as Graph
import           Data.IntMap                   (IntMap)
import qualified Data.IntMap                   as IntMap
import           Data.IntSet                   (IntSet)
import qualified Data.IntSet                   as IntSet
import qualified Data.Sequence                 as Seq
import qualified Data.Tree                     as Tree
{- integer-gmp -}
import           GHC.Integer.GMP.Internals
{- vector -}
import qualified Data.Vector                   as V
import qualified Data.Vector.Generic           as VG
import qualified Data.Vector.Generic.Mutable   as VGM
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Primitive         as VP
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

-------------------------------------------------------------------------------
-- main
-------------------------------------------------------------------------------
main :: IO ()
main = do
  (x, m) <- parse2
  a <- parseM m
  print $ flip mod 1000003 $ VU.sum $ VU.map (\i -> powModInt x i 1000003) a
powModInt :: Int -> Int -> Int -> Int
powModInt a b c = fromInteger $ powModInteger (fromIntegral a) (fromIntegral b) (fromIntegral c)
-------------------------------------------------------------------------------
-- 素数
-------------------------------------------------------------------------------
{-
primes :: [Int]
  素数列の無限リスト
primesToUA :: Int -> [Int]
  nまでの素数を列挙する
millerRabin :: Int -> Bool
  nが素数かどうか判定する
primeFactors :: Int -> [Int]
  nの素因数分解を求める
totient :: Int -> Int
  n以下の正整数でnと互いに素な数の個数
divisor :: Int -> [Int]
  nの約数を列挙する(未ソート)
nextPrimeInteger :: Integer -> Integer
  最強の関数 指定した数より大きい最初の素数を求める 素数を指定した場合も次の素数を返す
-}
sieveUA :: Int -> ArrU.UArray Int Bool
sieveUA top = ArrST.runSTUArray $ do
    let m = (top-1) `div` 2
        r = floor . sqrt $ fromIntegral top + 1
    sieve <- ArrST.newArray (1,m) True
    forM_ [1..r `div` 2] $ \i -> do
      isPrime <- ArrST.readArray sieve i
      when isPrime $ do
        forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> do
          ArrST.writeArray sieve j False
    return sieve
primesToUA :: Int -> [Int]
primesToUA top = 2 : [i*2+1 | (i,True) <- ArrU.assocs $ sieveUA top]

millerRabin :: Int -> Bool
millerRabin n
  |  n <= 1 = False
  |  n == 2
  || n == 3
  || n == 5
  || n == 7 = True
  |  even n = False
  |  otherwise = mrCheck $ fromIntegral n
powerMR :: Integer -> Integer -> Integer -> Integer
powerMR b e m = loop 1 (b `mod` m) e
  where
    loop res base pxe
      | pxe <= 0 = res
      | otherwise =
        let res'  = if pxe `mod` 2 == 1 then (res * base) `mod` m else res
            pxe'  = shift pxe (-1)
            base' = (base * base) `mod` m
        in loop res' base' pxe'
factoringPowers :: Integer -> (Integer, Integer)
factoringPowers n = loop (n - 1) 0
  where
    loop d s
      | even d    = loop (d `div` 2) (s + 1)
      | otherwise = (s, d)
mrCheck :: Integer -> Bool
mrCheck p
  | p < 2047                = loop [2]
  | p < 9080191             = loop [31,73]
  | p < 4759123141          = loop [2,7,61]
  | p < 1122004669633       = loop [2,13,23,1662803]
  | p < 2152302898747       = loop [2,3,5,7,11]
  | p < 341550071728321     = loop [2,3,5,7,11,13,17]
  | p < 3825123056546413051 = loop [2,3,5,7,11,13,17,19,23]
  | p < 9223372036854775808 = loop [2,325,9375,28178,450775,9780504,1795265022]
  | otherwise               = loop [ 2 .. min (p - 1) (floor $ 2 * (log p')^(2 :: Int)) ]
  where
    p' = fromIntegral p :: Double
    (s, d) = factoringPowers p
    loop [] = True
    loop (a:as)
      | (powerMR a d p) /= 1 && powLoop 0 = False
      | otherwise = loop as
      where
        powLoop r
          | r < s     = (powerMR a (2 ^ r * d) p) /= (p - 1)  && powLoop (r + 1)
          | otherwise = True
primeFactors :: Int -> [Int]
primeFactors a = let
                    (f, f1) = factorPairOf a
                    f' = if prime f then [f] else primeFactors f
                    f1' = if prime f1 then [f1] else primeFactors f1
                  in f' ++ f1'
  where
    factorPairOf a = let f = head $ factors a
                      in (f, a `div` f)
    factors a    = filter (isFactor a) [2..a-1]
    isFactor a b = a `mod` b == 0
    prime a      = null $ factors a
primes :: Integral a => [a]
primes = map fromIntegral $ [2, 3] ++ primes'
    where
      primes' = [5] ++ f 1 7 primes'
      f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
          where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
totient :: Int -> Int
totient n = n `quot` List.product ps * (List.product $ map (subtract 1) ps)
  where ps = map head . List.group $ primeFactors n
divisor :: Int -> [Int]
divisor n = List.foldr f [] $ List.takeWhile ((<= n) . (^ 2)) [1 .. n]
  where
    f x ds
        | r == 0, q /= x = x : q : ds
        | r == 0         = x : ds
        | otherwise      = ds
      where
        (q, r) = n `divMod` x
-------------------------------------------------------------------------------
-- 入力
-------------------------------------------------------------------------------
{-
parse1 2 3 4
  横に1,2,3,4個の空白区切りの数字をIntで読み取る
parseM m
  横にm個の空白区切りの数字をVU.Vector Intで読み取る
parseN n
  縦にn個の行区切りの数字をVU.Vector Intで読み取る
parseNM n m
  横にm個、縦にn個の数字をV.Vector (VU.Vector Int)で読み取る
parseCha
  文字列を一文字ずつVU.Vector Charで読み取る
-}
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine