#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, K, M;
int A[25050];
const int MOD = 1e9 + 7;
ll F[25050];
ll dp[4][25050][2];
ll X[4][25050];

ll pw(ll x, ll y = MOD - 2) {
	x %= MOD;
	ll res = 1;
	while(y) {
		if(y & 1) res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}
ll pwk[30030];

int exi_ans() {
	int cnt[404] = {}, cc = 0;
	for(int i=1;i<=K;i++) {
		int color = A[i];
		cc += (cnt[color] == 0);
		cnt[color]++;
	}
	if(cc == K) return 1;
	for(int i=K+1;i<=M;i++) {
		int c = A[i];
		cc += (cnt[c] == 0);
		cnt[c]++;
		c = A[i-K];
		cc -= (cnt[c] == 1);
		cnt[c]--;
		if(cc == K) return 1;
	}
	return 0;
}

int cucu[440], cuc;
int chk_unique(int* l, int* r) {
	++cuc;
	for(int *t=l;t<r;t++) {
		if(cucu[*t] == cuc) return 0;
		cucu[*t] = cuc;
	}
	return 1;
}

void add(ll &a, ll b) { a = (a + b) % MOD; }

void Fill(int t, int r = -1) {
	int suf[440] = {};
	if(r != -1) {
		for(int i=1;i<=r;i++) suf[i] = 1;
	}
	else {
		for(int i=1;i<K;i++) {
			if(i > 1 && suf[i-1] == 0) suf[i] = 0;
			else suf[i] = chk_unique(A+1+M-i, A+1+M);
		}
	}
	auto D = dp[t];
	ll sum[30030][2] = {};
	for(int i=1;i<=N;i++) rep(c, 2) {
		if(i < K) {
			if(suf[K-i] && c) add(D[i][c], F[i]);
		}
		else {
			if(c) add(D[i][c], F[K] * pwk[i-K] % MOD);
		}
		
		for(int j=i-1;j&&j>=i-K;j--) {
			add(D[i][c], D[j][!c] * F[i-j] % MOD);
		}
		if(i-K-1 >= 1) {
			add(D[i][c], sum[i-K-1][!c] * pwk[i-K] % MOD * F[K] % MOD);
		}
		add(sum[i][c], sum[i-1][c]);
		add(sum[i][c], D[i][c] * pw(pwk[i]) % MOD);
	}
	for(int i=0;i<=N;i++) {
		X[t][i] = (1 + sum[i][0] - sum[i][1] + MOD) * pwk[i] % MOD;
	}
}

ll ddp[25050][2][440][2];
ll f() {
	ddp[1][K==1?1:0][1][0] = K;
	if(M == 1) ddp[1][K==1?1:0][1][1] = K;
	for(int i=1;i<N;i++) {
		rep(c, 2) for(int d=1;d<=K;d++) {
			
			if(c == 0 && d == K-1) continue;
			add(ddp[i+1][c][1][0], ddp[i][c][d][0]);
			add(ddp[i+1][c][d+1][0], MOD - ddp[i][c][d][0]);
			
			add(ddp[i+1][c][1][1], ddp[i][c][d][1]);
			add(ddp[i+1][c][d+1][1], MOD - ddp[i][c][d][1]);
			
			if(d >= M) {
				add(ddp[i+1][c][M][1], ddp[i][c][d][0]);
				add(ddp[i+1][c][d+1][1], MOD - ddp[i][c][d][0]);
			}
		}
		rep(c, 2) for(int d=1;d<=K;d++) rep(e, 2) add(ddp[i+1][c][d][e], ddp[i+1][c][d-1][e]);
		
		rep(c, 2) for(int d=1;d<=K;d++) {
			int s = (c == 0 && d == K-1) ? 1 : d+1;
			
			for(int e=s;e<=d+1;e++) {
				ll lp = (e<=d?1:K-d);
				int nc = (c || e == K);
				add(ddp[i+1][nc][e][0], lp * ddp[i][c][d][0]);
				add(ddp[i+1][nc][e][1], lp * ddp[i][c][d][1]);
				if(e >= M) add(ddp[i+1][nc][e][1], lp * ddp[i][c][d][0]);
			}
		}
	}
	ll ans = 0;
	for(int d=1;d<=K;d++) {
		ans = (ans + ddp[N][1][d][1]) % MOD;
	}
	return ans * F[K-M] % MOD * pw(F[K]) % MOD;
}

int main() {
	F[0] = 1;
	for(int i=1;i<25050;i++) F[i] = i * F[i-1] % MOD;
	
	scanf("%d%d%d", &N, &K, &M);
	pwk[0] = 1; for(int i=1;i<30000;i++) pwk[i] = pwk[i-1] * K % MOD;
	for(int i=1;i<=M;i++) scanf("%d", A + i);
	if(M >= K && exi_ans()) {
		ll ans = (N - M + 1) * pw(K, N - M) % MOD;
		printf("%lld\n", ans);
	}
	else if(M < K && chk_unique(A+1, A+1+M)) {
		printf("%lld\n", f());
	}
	else {
		Fill(0);
		reverse(A+1, A+1+M);
		Fill(1);
		reverse(A+1, A+1+M);
		ll ans = 0;
		for(int i=0;i<=N-M;i++) add(ans, pwk[N-M] - X[0][i] * X[1][N-M-i] % MOD + MOD);
		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 346496