x, N = map(int, input().split())
ali = map(int, input().split())
res = 0
for a in ali:
    res += x ** a
print(res % 1000003)