using System;
using System.Linq;

namespace yukicoder
{
    class _016
    {
        static int[] p;
        static void Main()
        {
            int[] xn = Array.ConvertAll(Console.ReadLine().Split(' ')
                , x => int.Parse(x));
            int[] an = Array.ConvertAll(Console.ReadLine().Split(' ')
                , x => int.Parse(x));
            int m = an.Max();
            p = new int[m + 1];
            int l = c(xn[0], m);
            int ans = 0;
            foreach(int a in an)
            {
                ans += p[l == 1 ? a : a % l];
            }
            Console.WriteLine(ans % 1000003);
        }
        static int c(int x, int m)
        {
            int l = 1;
            p[0] = 1;
            for (int i = 1; i < m + 1; i++)
            {
                p[i] = p[i -1] * x % 1000003;

                if (p[i] == 1)
                {
                    return i;
                }
            }
            return l;
        }
    }
}