# -*- coding: utf-8 -*-

X,N = map(int,input().split())

lstin  = list(map(int,input().split()))

valsum = 0

for val in lstin:
    valsum = valsum +X**val
    
print(valsum % 1000003)