using System;
using System.Linq;

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