# -*- coding: utf-8 -*-
def calc(x, n):
    flag = 1
    if n == 0:
        return 1
    p = 1
    while flag == 1:
        nn = n // 2
        mm = n % 2
        p *= x ** mm
        if nn == 0:
            flag = 0
        else:
            x *= x
            n = nn
    return p % 1000003


x, N = map(int, raw_input().split())
n = map(int, raw_input().split())
tot = 0
for i in range(0, N):
    tot += calc(x, n[i]) % 1000003
print tot