import math
    
x, n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

ans = 0
for i in range(n):
  ans += pow(x, a[i], 1000003)

print(ans % 1000003)