import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

x, n= map(int, input().split())
a = list(map(int, input().split()))

ans = 0
for i in range(n):
  ans += pow(x, a[i], 1000003)

print(ans % 1000003)