#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

#define FOR(x,y) for(int x = 0;x < y;x++)
#define LLI long long int
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())

template<int um> class UF {
public:
    vector<int> _parent,_rank;
    UF()
    {
        _parent=_rank=vector<int>(um,0);
        for(int i=0;i<um;i++)
        {
            _parent[i]=i;
        }
    }
    
    int Find(int x)
    {
        if(_parent[x] == x)
        {
            return x;
        }
        _parent[x] = Find(_parent[x]);
        return _parent[x];
    }
    
    int Union(int x,int y)
    {
        int xRoot = Find(x);
        int yRoot = Find(y);
        if(_rank[xRoot]>_rank[yRoot])
        {
            _parent[xRoot] = yRoot;
           return yRoot;
        }
        if(_rank[xRoot]<_rank[yRoot])
        {
            _parent[yRoot] = xRoot;
            return xRoot;
        }
        if(xRoot != yRoot)
        {
            _parent[yRoot] = xRoot;
            _rank[xRoot]++;
            return xRoot;
        }
        return xRoot;
    }
};

map<LLI,int> counts;
const LLI mod = 1000003;

LLI Build(LLI a, const vector<LLI> bits)
{
    LLI r = 1;
    int i = 0;
    while(a > 0)
    {
        if((a & 1) ==1)
        {
            r *= bits[i];
            r %= mod;
        }
        i++;
        a >>= 1;
    }
    return r;
}

int main() {
    int x, N;
    cin >> x >> N;
    FOR(i, N)
    {
        LLI a;
        cin >> a;
        counts[a]++;
    }
    vector<LLI> bits;
    LLI k = x;
    bits.push_back(k);
    LLI c = 1;
    while(c <= 100000000)
    {
        k = k * k;
        k %= mod;
        c *= 2;
        bits.push_back(k);
    }
    LLI result = 0;
    FORR(r, counts)
    {
        LLI m = Build(r.first, bits);
        m *= r.second;
        m %= mod;
        result += m;
        result %= mod;
    }
    cout << result << endl;
    return 0;
}