#include <iostream>
using namespace std;

int main(void){
    int x, N, a, tmp, ans = 0;

    cin >> x >> N;
    while(N--){
        cin >> a;
        tmp = 1;
        while(a--){
            tmp *= x;
            tmp %= 1'000'003;
        }
        ans += tmp;
    }
    cout << ans%1'000'003 << endl;

    return 0;
}