using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        string[] ary = Console.ReadLine().Split();
        int x = int.Parse(ary[0]);
        int n = int.Parse(ary[1]);

        long[] su = Console.ReadLine().Split().Select(v => long.Parse(v)).ToArray();

        long ans = 0;

        for (int i = 0; i < n; i++)
        {
            ans += (long)(Math.Pow(x, su[i]) % 1000003);
        }

        Console.WriteLine(ans);
        Console.ReadLine();
    }
}