import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

x, n, *a = map(int, read().split())
ans = 0
mod = 10 ** 6 + 3
for aa in a:
    ans += pow(x, aa, mod)
    ans %= mod
print(ans)