using System;
using System.Linq;

class Program
{
    static int m = 1000003;
    static void Main()
    {
        var s = Console.ReadLine().Split();
        long x = long.Parse(s[0]);
        long n = long.Parse(s[1]);
        var a = Console.ReadLine().Split().Select(long.Parse).ToArray();

        long ans = 0;

        for (int i = 0; i < n; i++)
        {
            ans = pow(x, a[i]) % m;
        }

        Console.WriteLine(ans);
    }

    static long pow(long a,long n)
    {
        if (n == 0) return 1;
        long res = pow(a * a % m, n / 2);
        if (n % 2 == 1) res *= res * a % m;
        return res;
    }
}