import sys
sys.setrecursionlimit(200000)
mod = 1000003
x, n = map(int, input().split())
def g(a):
    if a == 0:
        return 1
    if a == 1:
        return x
    return g(a // 2) ** 2 * g(a & 1) % mod
print(sum(g(i) for i in map(int, input().split())) % 1000003)