x, n = [int(s) for s in input().split()] a = [int(s) for s in input().split()] mod = 10**6 + 3 def powmod(ai, mod, memo): if ai in memo: return memo[ai] res = 0 if ai == 0: res = 1 elif ai % 2 == 0: pw = powmod(ai // 2, mod, memo) res = pw * pw % mod else: pw = powmod((ai - 1) // 2, mod, memo) res = x * pw * pw % mod if len(memo) < 10000000: memo[ai] = res return res memo = {} res = 0 for ai in a: res = (res + powmod(ai, mod, memo)) % mod print(res)