using System.Numerics;

public class Program
{
    public static void Main()
    {

        //BigInteger num = BigInteger.Parse(Console.ReadLine() ?? string.Empty);
        //int num = int.Parse(Console.ReadLine() ?? string.Empty);
        string[] moji = (Console.ReadLine() ?? string.Empty).Trim().Split(' ');
        string[] str = (Console.ReadLine() ?? string.Empty).Trim().Split(' ');
        //string str = Console.ReadLine() ?? string.Empty;


        int x = int.Parse(moji[0]);
        int n = int.Parse(moji[1]);

        BigInteger big = 0;
        for(int i = 0;i<n;i++)
        {
            big += (BigInteger)Math.Pow(x, double.Parse(str[i]));
        }
        big %= 1000003;
        Console.WriteLine(big);
        
    }
}