# -*- coding: utf-8 -*-
x, N = map(int, raw_input().split())
n = map(int, raw_input().split())
A = [1 for i in range(0, max(n)+1)]
tmp = 1
A[0] = 1
for i in xrange(1, max(n)+1):
    tmp *= x % 1000003
    A[i] = tmp
tot = 0
for i in xrange(0, N):
    tot += A[n[i]]
print tot % 1000003