using System;
using System.Linq;

class Program
{
    static int m = 1000003;
    static void Main()
    {
        var s = Console.ReadLine().Split();
        long x = long.Parse(s[0]);
        long n = long.Parse(s[1]);
        var a = Console.ReadLine().Split().Select(long.Parse).ToArray();

        long ans = 0;

        for (int i = 0; i < n; i++)
        {
            ans += pow(x, a[i]) % m;
        }
        Console.WriteLine(ans);
    }

    static long pow(long a,long n)
    {
        if (n == 0) return 1;
        long res = pow((a % m) * (a % m) % m, n / 2);
        if (n % 2 == 1) res = res * (a % m) % m;
        return res;
    }
}