import sys

def solve():
    x, N = map(int, input().split())
    A = [int(i) for i in input().split()]
    mod = 10**6 + 3

    ans = sum(pow(x, a, mod) for a in A)
    ans %= mod

    print(ans)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()