using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
		var line1 = Console.ReadLine().Split(' ').Select(c => int.Parse(c)).ToArray();
		int x = line1[0];
		int n = line1[1];
		
		var array = Console.ReadLine().Split(' ').Select(c => int.Parse(c)).ToArray();
		
		int remainder = 0;
		int divide = 1000003;
		
		for(int i = 0;i < n;i++)
		{
			int a = 1;
			for(int p = 0;p < array[i];p++)
			{
				a *= x;
				int b = a / divide;
				a -= b * divide;
			}
			remainder += a;
			
		}
		Console.WriteLine(remainder % divide);
    }
}