#include<stdio.h>
int pow(long long x,int n);
int M = 1000003;
main(){
    int X,N;
    scanf("%d%d",&X,&N);
    long long sum = 0;
    for(int i = 0;i < N;i++){
        int a;
        scanf("%d",&a);
        sum += pow(X,a);
    }
    printf("%d\n",sum%M);

}
//x^nを求める
int pow(long long x,int n){
    if(n == 0){return 1;}
    int ans = pow(x*x%M,n/2);
    if(n%2 == 1){
        ans = ans*x % M;
    }
    return ans;
}