M = 10 ** 6 + 3


def mod_pow(x, n):
    res = 1
    while n:
        if n & 1:
            res = res * x % M
        x = x * x % M
        n >>= 1

    return res


def main():
    x, n = map(int, input().split())
    a = list(map(int, input().split()))

    ans = 0
    for i in a:
        ans = (ans+mod_pow(x, i)) % M

    print(ans)


if __name__ == '__main__':
    main()