def pow(n):
    ans=1
    e=x
    for i,c in enumerate(bin(int(n))[:1:-1]):
        if c=="1":ans=(ans*e)%1000003
        e=(e*e)%1000003
    return ans

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