let i = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')
let M = 1000003
let x = parseInt(i[0])
let a = i[1].split(' ').map((e) => {
  let n = parseInt(e)
  return Math.floor(n / M) + (n % M)
})
let r = 0
a.forEach((e) => {
  let p = 1
  for (let c = 0; c < e; c++) {
    p *= x
    p %= M
  }
  r += p
  r %= M
})
console.log(r)