#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<iomanip>

#include<cmath>

#include<string>

#include<vector>

using namespace std;

__int64 mod=;

int dis[],data[],next[];

__int64 euler(__int64 n)

{

    int i;

    __int64 ans=;

    for(i=;i*i<=n;i++)

        if(n%i==)

        {

            ans*=i-;

            n/=i;

            while(n%i==)

            {

                ans*=i;

                n/=i;

            }

        }

    if(n>) ans*=n-;

    return ans%mod;

}

int get_next(int n)

{

    int i=,j=-;

    next[]=-;

    while(i<n)

    {

        if(j==-||dis[i]==dis[j])

        {

            i++;

            j++;

            next[i]=j;

        }

        else j=next[j];

    }

    i=n-j;

    if(n%i)

        return n;

    return i;

}

__int64 pows(__int64 a,__int64 b)

{

    __int64 ans=;

    a%=mod;

    while(b)

    {

        if(b&) ans=(ans*a)%mod;

        b>>=;

        a=(a*a)%mod;

    }

    return ans%mod;

}

__int64 polya(__int64 m,__int64 n)

{

    int i,j;

    __int64 ans=;

    for(i=;i*i<=n;i++)

    {

        if(n%i==)

        {

            ans=(ans+pows(m,n/i)*euler(i)%mod)%mod;

            if(i*i!=n)

                ans=(ans+pows(m,i)*euler(n/i)%mod)%mod;

        }

    }

    return (ans*pows(n,mod-))%mod;

}

int main()

{

    int n,i,j,k,t,m,s,p;

    while(cin>>s>>p)

    {

        if(s==-&&p==-) break;

        for(i=;i<p;i++) cin>>data[i];

        sort(data,data+p);

        for(i=;i<p;i++)

            dis[i]=data[i]-data[i-];

        dis[]=-data[p-]+data[];

        int len=get_next(p);

        printf("%I64d\n",polya(pows(s,len),p/len));

    }

    return ;

}