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