import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X, N = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    MOD = 1000003

    ans = 0
    for a in A:
        ans += pow(X, a, MOD)
        ans %= MOD

    print(ans % MOD)




if __name__ == '__main__':
    main()