mod = 1000003
x, N = map(int,input().split())
ans = 0

for a in map(int, input().split()):
    ans += pow(x, a, mod)
    if ans >= mod:
        ans -= mod
print(ans)