#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2005, M = 1e7 + 5, mod = 1e9 + 7;
int typ, n, K, pnum, ans;
int pri[664600], tmp[M], cnt[M], g[M], a[M], bo[M];
int sum[N], p[N][N], gcd[N][N], num[N][N];

void up(int &x, int y) { x += y; if (x >= mod) x -= mod; if (x < 0) x += mod; }

void init() {
    for (int i = 1; i <= n; ++i) {
        p[i][0] = 1;
        for (int j = 1; j <= n; ++j) p[i][j] = (LL)p[i][j - 1] * i % K;
    }
    for (int i = 1; i <= n; ++i) 
        gcd[0][i] = gcd[i][0] = gcd[i][i] = i, gcd[i][1] = gcd[1][i] = 1;
    for (int i = 2; i <= n; ++i)
        for (int j = 2; j < i; ++j) {
            if (!gcd[i][j]) gcd[i][j] = gcd[j][i - j];
            gcd[j][i] = gcd[i][j];
        }
    sum[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1, k = 1; k <= i; k += 3 * j + 1, ++j)
            up(sum[i], (LL)sum[i - k] * (j & 1 ? 1 : -1));
        for (int j = 1, k = 2; k <= i; k += 3 * j + 2, ++j)
            up(sum[i], (LL)sum[i - k] * (j & 1 ? 1 : -1));
    }
    g[0] = 0; g[1] = 1;
    for (int i = 2; i < M; ++i) {
        if (!bo[i]) pri[++pnum] = i, tmp[i] = i, g[i] = 2 * (i - 1);
        for (int j = 1; j <= pnum && (LL)i * pri[j] < M; ++j) {
            bo[i * pri[j]] = 1;
            if (!(i % pri[j])) {
                tmp[i * pri[j]] = tmp[i] * pri[j];
                if (tmp[i] ^ i) g[i * pri[j]] = (LL)g[i / tmp[i]] * g[tmp[i] * pri[j]] % mod;
                else g[i * pri[j]] = ((LL)pri[j] * g[i] + i * pri[j] - i) % mod;
                break;
            }
            tmp[i * pri[j]] = pri[j];
            g[i * pri[j]] = (LL)g[i] * g[pri[j]] % mod;
        }
    }
}

int f(int x, int y) {
    if (typ == 1) return 1 % K;
    if (typ == 2) return gcd[x][y] % K;
    return (p[x][y] + p[y][x] + (x ^ y)) % K;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("BZOJ4772.in", "r", stdin);
    freopen("BZOJ4772.out", "w", stdout);
#endif
    scanf("%d%d%d", &typ, &n, &K);
    for (int i = 0; i < K; ++i) scanf("%d", &a[i]);
    init();
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; i + j <= n; ++j) {
            int t = f(i, j);
            for (int ni = 1; ni * i + j <= n; ++ni)
                for (int nj = 1; ni * i + nj * j <= n; ++nj)
                    up(cnt[t], sum[n - ni * i - nj * j]);
        }
    for (int i = 1; i <= n; ++i) {
        int t = f(i, i);
        for (int ni = 1; ni * i <= n; ++ni) {
            int s = sum[n - ni * i];
            if ((ni + 1) * i <= n) up(s, -sum[n - (ni + 1) * i]);
            up(cnt[t], (LL)ni * (ni - 1) / 2 * s % mod);
        }
    }
    for (int i = 0; i < K; ++i) up(ans, (LL)cnt[i] * g[a[i]] % mod);
    printf("%d\n", ans);

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=2005,M=1e7+5,mod=1e9+7;
int typ,n,K,pnum,ans;
int pri[664600],tmp[M],cnt[M],g[M],a[M],bo[M];
int sum[N],p[N][N],gcd[N][N],num[N][N];

void up(int &x,int y) {x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;}

void init()
{
    for(int i=1;i<=n;++i)
    {
        p[i][0]=1;
        for(int j=1;j<=n;++j) p[i][j]=(LL)p[i][j-1]*i%K;
    }
    for(int i=1;i<=n;++i) 
        gcd[0][i]=gcd[i][0]=gcd[i][i]=i,gcd[i][1]=gcd[1][i]=1;
    for(int i=2;i<=n;++i)
        for(int j=2;j<i;++j)
        {
            if(!gcd[i][j]) gcd[i][j]=gcd[j][i-j];
            gcd[j][i]=gcd[i][j];
        }
    sum[0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=1,k=1;k<=i;k+=3*j+1,++j)
            up(sum[i],(LL)sum[i-k]*(j&1?1:-1));
        for(int j=1,k=2;k<=i;k+=3*j+2,++j)
            up(sum[i],(LL)sum[i-k]*(j&1?1:-1));
    }
    g[0]=0;g[1]=1;
    for(int i=2;i<M;++i)
    {
        if(!bo[i]) pri[++pnum]=i,tmp[i]=i,g[i]=2*(i-1);
        for(int j=1;j<=pnum && (LL)i*pri[j]<M;++j)
        {
            bo[i*pri[j]]=1;
            if(!(i%pri[j]))
            {
                tmp[i*pri[j]]=tmp[i]*pri[j];
                if(tmp[i]^i) g[i*pri[j]]=(LL)g[i/tmp[i]]*g[tmp[i]*pri[j]]%mod;
                else g[i*pri[j]]=((LL)pri[j]*g[i]+i*pri[j]-i)%mod;
                break;
            }
            tmp[i*pri[j]]=pri[j];
            g[i*pri[j]]=(LL)g[i]*g[pri[j]]%mod;
        }
    }
}

int f(int x,int y)
{
    if(typ==1) return 1%K;
    if(typ==2) return gcd[x][y]%K;
    return (p[x][y]+p[y][x]+(x^y))%K;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("BZOJ4772.in","r",stdin);
    freopen("BZOJ4772.out","w",stdout);
#endif
    scanf("%d%d%d",&typ,&n,&K);
    for(int i=0;i<K;++i) scanf("%d",&a[i]);
    init();
    for(int i=1;i<=n;++i)
        for(int j=i+1;i+j<=n;++j)
        {
            int t=f(i,j);
            for(int ni=1;ni*i+j<=n;++ni)
                for(int nj=1;ni*i+nj*j<=n;++nj)
                    up(cnt[t],sum[n-ni*i-nj*j]);
        }
    for(int i=1;i<=n;++i)
    {
        int t=f(i,i);
        for(int ni=1;ni*i<=n;++ni)
        {
            int s=sum[n-ni*i];
            if((ni+1)*i<=n) up(s,-sum[n-(ni+1)*i]);
            up(cnt[t],(LL)ni*(ni-1)/2*s%mod);
        }
    }
    for(int i=0;i<K;++i) up(ans,(LL)cnt[i]*g[a[i]]%mod);
    printf("%d\n",ans);

    return 0;
}