import sys
mod = 1000003
x, n = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
s = 0
x %= mod
for k in a:
    s = (s + pow(x, k, M)) % M
print(s)