from functools import lru_cache

@lru_cache(maxsize=None)
def f(x, n):
    return x ** n

def g():
    x, _ = map(int, input().split())
    l = sorted(map(int, input().split()))
    
    n = f(x, l[0])
    yield n
    
    for i in map(lambda it: it[1]-it[0], zip(l[:-1], l[1:])):
        n *= f(x, i)
        yield n

print(sum(g()) % 1000003)