x, n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

print(x ** sum(a) % 1000003)