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)
        {
            var p = 0L;
            for (int j=0;j<k[i];++j)
            {
                p = line[0] * line[0];
                p /= 1000003;
            }
            ans += (long)p;
            ans %= 1000003;
        }
        Console.WriteLine(ans);
    }
}