def sol x,n,mod
    ans = 1
    while n > 0
        if (n & 1) == 1
            ans = (ans * x) % mod
        end
        n = n >> 1
        x = (x * x) % mod
    end
    return ans
end

x,N = gets.split.map(&:to_i)
MOD = 1000003
p gets.split.map{|a|sol(x,a.to_i,MOD)}.inject(:+) % MOD