#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k>>=1;
    }
    return ans;
}
ll inv(ll a){
	return powmod(a, MOD-2);
}
int main()
{
    int n, k, m; cin>>n>>k>>m;
    if(k>n){
        cout<<0<<endl;
        return 0;
    }
    int a[25010];
    for(int i=0; i<m; i++){
        cin>>a[i];
    }
    if(k<=m){
        map<int, int> mp;
        for(int i=0; i<k; i++) mp[a[i]]++;
        if(mp.size()==k){
            cout<<(n-m+1)*powmod(k, n-m)%MOD<<endl;
            return 0;
        }
        for(int i=k; i<m; i++){
            mp[a[i-k]]--;
            mp[a[i]]++;
            if(mp[a[i-k]]==0) mp.erase(a[i-k]);
            if(mp.size()==k){
                cout<<(n-m+1)*powmod(k, n-m)%MOD<<endl;
                return 0;
            }
        }
    }
    int x[410];
    fill(x, x+k+1, -1);
    int p=-1, q=-1;
    for(int i=0; i<m; i++){
        if(x[a[i]]>=0 && x[a[i]]>i-k){
            p=i;
            break;
        }
        x[a[i]]=i;
    }
    fill(x, x+k+1, -1);
    for(int i=m-1; i>=0; i--){
        if(x[a[i]]>=0 && x[a[i]]<i+k){
            q=i;
            break;
        }
        x[a[i]]=i;
    }
    if(p==-1){
        ll dp[2][25010][410]={};
        dp[0][0][1]=k;
        ll f=1;
        for(int i=0; i<m; i++) (f*=(k-i))%=MOD;
        f=inv(f);
        for(int i=0; i<n; i++){
            for(int j=m; j<k; j++) (dp[1][i][j]+=dp[0][i][j]*f)%=MOD;
            for(int j=1; j<k; j++){
                for(int l=0; l<2; l++) (dp[l][i+1][j]+=dp[l][i][j])%=MOD;
            }
            for(int j=k-2; j>=1; j--){
                for(int l=0; l<2; l++) (dp[l][i+1][j]+=dp[l][i+1][j+1])%=MOD;
            }
            for(int j=1; j<k-1; j++){
                for(int l=0; l<2; l++) (dp[l][i+1][j+1]+=dp[l][i][j]*(k-j))%=MOD;
            }
        }
        ll ans=0;
        for(int j=1; j<k; j++) (ans+=dp[1][n-1][j])%=MOD;
        ans=((n-m+1)*powmod(k, n-m)-ans+MOD)%MOD;
        cout<<ans<<endl;
        return 0;
    }
    ll dp[25010][410]={}, dp2[25010][410]={};
    ll s[25010]={}, s2[25010]={};
    dp[0][p]=1;
    for(int i=0; i<n; i++){
        for(int j=1; j<k; j++){
            (dp[i+1][j]+=dp[i][j])%=MOD;
        }
        for(int j=k-2; j>=1; j--){
            (dp[i+1][j]+=dp[i+1][j+1])%=MOD;
        }
        for(int j=1; j<k-1; j++){
            (dp[i+1][j+1]+=dp[i][j]*(k-j))%=MOD;
        }
    }
    for(int i=0; i<=n; i++) for(int j=1; j<k; j++) (s[i]+=dp[i][j])%=MOD;
    q=m-1-q;
    dp2[0][q]=1;
    for(int i=0; i<n; i++){
        for(int j=1; j<k; j++){
            (dp2[i+1][j]+=dp2[i][j])%=MOD;
        }
        for(int j=k-2; j>=1; j--){
            (dp2[i+1][j]+=dp2[i+1][j+1])%=MOD;
        }
        for(int j=1; j<k-1; j++){
            (dp2[i+1][j+1]+=dp2[i][j]*(k-j))%=MOD;
        }
    }
    for(int i=0; i<=n; i++) for(int j=1; j<k; j++) (s2[i]+=dp2[i][j])%=MOD;
    ll ans=(n-m+1)*powmod(k, n-m)%MOD;
    for(int i=0; i<=n-m; i++){
        (ans+=(MOD-s[i]*s2[n-m-i]%MOD))%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 162944