x, n = map(int,input().split())
power_list = list(map(int, input().split()))
ans = 0
for i in power_list:
    ans += x**i
print(ans % 1000003)