#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<55)+1e9; // ~ 3.6 * 1e16
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
ostream& operator<<(ostream& o,T t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){Int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

class CumulativeSum{
public:
  vector<Int> sum;
  CumulativeSum(){}
  CumulativeSum(const vector<Int> &A){init(A);}
  void init (const vector<Int> &A){
    sum.clear();
    Int n = A.size();
    sum.resize(n+1,0);
    for(Int i=1;i<=n;i++) sum[i] = (sum[i] + sum[i-1] + A[i-1])%mod;
  }
  
  Int get(Int l,Int r){
    assert(l<=r && l>=0 && r<=(Int)sum.size());
    return (sum[r] - sum[l] + mod)%mod;
  } //[l,r)
};

ll factorial(Int i){
  static vector<ll> k(1e6);
  if(!k[0]){k[0]=1;for(Int i=1;i<(Int)k.size();i++)k[i]=i*k[i-1]%mod;}
  return k[i];
}

ll mod_pow(ll x,ll n){
  ll res=1;
  while(n){
    if(n%2) res=res*x%mod;
    x=x*x%mod;
    n/=2;
  }
  return res;
}

ll inv(Int x){ return mod_pow(x, mod-2);}
ll nPm(Int n,Int m){return factorial(n) * inv(factorial(n - m)) % mod;}

Int N, K, M;
vector<vector<Int> > dp; //i文字使って、最後のj文字がユニークになる通り数。
void DP(){
  dp = vector<vector<Int> > (N+1, vector<Int>(K+1,0));

  dp[0][0] = 1;
  CumulativeSum Sum(dp[0]);
  for(Int i=1;i<=N;i++){
    for(Int j=1;j<K;j++){
      dp[i][j] = Sum.get(j, K) + dp[i-1][j-1] * (K-j + 1);
      dp[i][j] %= mod;
    }
    Sum.init(dp[i]);
  }
}


Int solve1(vector<Int> A){
  Int x = 0, y = 0;
  {
    set<Int> S;
    while(!S.count(A[x])) S.insert(A[x]), x++;
  }

  {
    set<Int> S;
    while(!S.count(A[M-y-1])) S.insert(A[M-y-1]), y++;
  }
  assert(x < K && y < K);
  
  Int ans = 0;
  for(Int i=0;i<N;i++){
    Int I = i + x;
    Int J = N - (i+M) + y;
    if(I < 0 || I > N || J < 0 || J > N) continue;
    assert(I + J + M-x-y == N);
    Int X = 0, Y = 0;

    for(Int j = x; j < K ; j++) {
      if(I < j) continue;
      Int num = dp[I][j];
      X = (X + num) % mod;
    }
    X = X * inv(nPm(K, x)) % mod;
    
    for(Int j = y; j < K ; j++){
      if(J < j) continue;
      Int num = dp[J][j];
      Y = (Y + num) % mod;
    }
    Y = Y * inv(nPm(K, y)) % mod;
    
    ans = (ans + X * Y) % mod;
  }
  return ans;
}

vector<vector<Int> > dp2; //i文字使って、末尾j個のカラフルな数列で丁度長さMのユニークな区間をを持つ数列の通り数。
Int solve2(vector<Int> A){
  dp2 = vector<vector<Int> > (N+1, vector<Int>(K+1,0));
  dp[0][0] = 1;
  CumulativeSum Sum(dp2[0]);
  for(Int i = 1;i <= N; i++){
    for(Int j= 1;j < K ; j++){
      Int a = dp[i][j] * (j >= M);
      Int b = dp2[i-1][j-1] * (K-j+1) % mod; //前回の数列から1増える
      Int c = Sum.get(j, K);
      dp2[i][j] = a + b + c;
      dp2[i][j] %= mod;
    }
    Sum.init(dp2[i]);
  }
  
  Int ans = 0;
  for(Int i=1;i<K;i++) ans = (ans + dp2[N][i]) % mod;
  ans = ans * inv(nPm(K,M))% mod;
  return ans;
}

Int calcAll(){
  return (N - M + 1) * mod_pow(K, N - M) % mod;
}


Int solve(vector<Int> A){
  auto tmp = A;
  sort(tmp.begin(), tmp.end());
  tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
  Int num = calcAll();
  DP();
  Int cnt = 0;
  {
    set<Int> S;
    queue<int> Q;
    for(Int a:A){
      while(S.count(a)) S.erase(Q.front()), Q.pop();
      S.insert(a), Q.push(a);
      if((Int)S.size() == K) cnt++;
    }
  }
  if(cnt != 0) return (num + (cnt-1))% mod;
  if(A.size() != tmp.size()) return (num - solve1(A) + mod) % mod;
  return (num - solve2(A) + mod) % mod;
}

signed main(){
  cout << fixed << setprecision(12);
  
  cin>>N>>K>>M;
  vector<Int> A(M);
  cin>>A;
  pr(N,M,K,A);
  Int ans = solve(A);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 166272