# -*- coding: utf-8 -*-

# x N
# a1 a2 … aN

x, N = map(int, raw_input().split())
a = map(int, raw_input().split())

total = 0
for i in xrange(N):
    total += x ** a[i]

print total % 1000003