from math import log10 # import sys # sys.setrecursionlimit(100000) x, N = map(int, input().split()) a = list(map(int, input().split())) xp = 0 n = 1000003 j = 0 def keta(x, a): ketasuu = int(a * log10(x)) + 1 return ketasuu def amari(x, a, n): if keta(x, a) <= 14: return (x ** a) % n else: makexp(x, n) result = 0 r = a // xp result = (x ** (a % xp)) * amari(j, r, n) result = result % n return result def makexp(x, n): global xp global j if x > 1: i = 0 while(True): if x ** i > n: xp = i j = x ** i - n return None break i += 1 shiguma = 0 for i in range(N): shiguma += amari(x, a[i], n) shiguma = shiguma % n print(shiguma)