main::IO()
main =do
  xi:_:[] <- fmap (fmap read . words) getLine
  xsi <- fmap (fmap read . words) getLine
  let moda =1000003
      hyou 0 _ = []
      hyou n g =  cal:hyou (n-1) cal
                  where cal = (g * g) `mod` moda 
      xtenkai 0 = []
      xtenkai x = (x `mod` 2 ==1):xtenkai (x `div` 2)
  print . (`mod` moda) . sum . map (\x-> 
               foldl (\acc (a,b) ->if b then acc*a else acc) 1 .
               zip (xi:hyou 31 xi) $ xtenkai x
               ) $xsi