g = lambda x: lambda s: x ** int(s)

x, N = map(int, input().split())
f = g(x)
print(sum(map(f, input().split())) % 1000003)