import std.stdio;
import std.string;
import std.array;
import std.algorithm;
import std.conv;

void main() {
    ulong x, n; readf("%s %s\n", &x, &n);
    ulong[] a = readln.strip.split.map!(to!ulong).array;

    const ulong M = 1000003;
    ulong[] m = new ulong[a[n-1] + 1];
    m[0] = 1;
    if (0 < a[n-1]) { m[1] = x % M; }
    foreach (i; 2..(a[n-1]+1)) {
        m[i] = (m[i-1] * m[1]) % M;
    }
    writeln(a.map!(ai => m[ai]).sum % M);
}