import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x,n,*A = map(int,read().split())

MOD = 10 ** 6 + 3
answer = sum(pow(x,a,MOD) for a in A) % MOD
print(answer)