import sys
readline = sys.stdin.readline
read = sys.stdin.read

x,n,*a = map(int,read().split())
MOD = 1000003
print(sum(map(lambda c:pow(x,c,MOD),a))%MOD)