x, cnt = map(int,input().split())
ans = 0
a = list(int(i) for i in input().split())
for _ in range(cnt):
    ans += x ** a[_]
print(ans%1000003)