x, N = map(int,input().split()) A = list(map(int,input().split())) MOD = 10**6 + 3 ans = 0 for a in A: ans += pow(x, a, MOD) ans %= MOD print(ans)