using System;
using System.Linq;

class No16
{
    static void Main()
    {
        var line = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var k = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var ans = 0L;
        for (int i = 0; i < line[1]; ++i)
        {
            ans += (long)Math.Pow(line[0], k[i]);
            ans /= 1000003;
        }
        Console.WriteLine(ans);
    }
}