main::IO()
main = do
  xi:_:[] <- fmap (fmap read . words) getLine
  xsi <- fmap (fmap read . words) getLine
  let f1 _ [] = 0
      f1 xi (x:xs) = xi^x + f1 xi xs
  print . (`mod` 1000003) $ f1 xi xsi