X, N = map(int, input().split()) A = list(map(int, input().split())) MOD = 1000003 ans = 0 for i in range(N): ans += pow(X, A[i], MOD) print(ans % MOD)