let modVal = 1000003
let genPowModSeq n = Seq.unfold(fun x -> Some(x,x*n%modVal)) 1

let x,N  = let t = stdin.ReadLine().Split() |> Array.map(int) in t.[0],t.[1]
let a    = stdin.ReadLine().Split() |> Array.map(int)

let pows = genPowModSeq x |> Seq.take 1000000001 |> Seq.toArray
let ans  = a |> Array.sumBy(fun x -> pows.[x])

ans |> printfn "%A"