using System;

namespace yukicoder
{
    class _016
    {
        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 ans = 0;
            foreach(int a in an)
            {
                ans += p(xn[0], a);
            }
            Console.WriteLine(ans % 1000003);
            Console.ReadLine();

        }
        static int p(int x, int a)
        {
            int ret = 1;
            for (int i = 0; i < a; i++)
            {
                ret = ret * x % 1000003;
            }

            return ret;
        }
    }
}