import sys
input = lambda :sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
ms = lambda: map(str, input().split())
mf = lambda: map(float, input().split())
li = lambda: list(mi())

def main():
    x, N = mi()
    a = li()
    ans = 0
    mod = int(1e6) + 3
    for i in range(N):
        ans += pow(x, a[i], mod)
        ans %= mod
    print(ans)
    


if __name__ == '__main__':
    main()