-- yukicoder My Practice
-- author: Leonardone @ NEETSDKASU

-- http://yukicoder.me/problems/42

import Data.List
import qualified Data.Map as Map

main = do
    xn <- getLine
    a <- getContents
    putStrLn $ solve xn a

solve xn a = show ans
    where
        (x:_) = map read $ words xn
        an = map read $ words a
        ans = foldl (\t ai -> modval $ t + (pow x ai)) 0 an

modval v = mod v 1000003

pow x n
    | n == 0    = 1
    | n == 1    = modval $ x
    | m == 0    = vv
    | otherwise = modval $ x * vv
    where
        (d, m) = divMod n 2
        v = modval $ pow x d
        vv = modval $ v * v