#include <iostream>
using namespace std;

#define N 100000000
#define Q 1000003

int main(void){
  int x,n;
  int dp[N+1], ans;
  
  cin >> x >> n;
  dp[1] = x;
  for (int i=2; i<=N; i++){
    long long tmp = dp[i/2]*dp[i/2] % Q;
    if (i%2) tmp = tmp*x % Q;
    dp[i] = tmp;
  }
  ans = 0;
  for (int i=0; i<n; i++){
    int a;
    cin >> a;
    ans += dp[a];
    ans %= Q;
  }
  cout << ans << endl;
  return 0;
}