def pow(n):
    ans=1
    e=x
    n=int(n)
    while n:
        if n&1:ans=(ans*e)%1000003
        n//=2
        e=(e*e)%1000003
    return ans

x=int(input().split()[0])
print(sum(map(pow,input().split()))%1000003)